Imtiyozli navbatlar

Imtiyozli navbatlar.

Amalda, uyumlarni saralash eng tezkor emas - umuman, tez tortish tezroq. Biroq, uyumning o'zi ko'pincha ma'lumotlar tuzilishi sifatida foydalidir. Ushbu bo'limda biz uyumga asoslangan ustuvor navbatni modellashtirishni ko'rib chiqamiz - ulardan biri uyumdan foydalanishning eng mashhur namunalari.

Imtiyozli navbat - bu elementlari bo'lgan S to'plamidir Biz buni raqamlar sifatida ko'rib chiqamiz. Amalda S to'plamining elementlari quyidagilardir juftliklar {key, α}, bu erda kalit - elementning ustuvorligini belgilaydigan va chaqirilgan raqam kalit (kalit) va α - unga tegishli ma'lumotlar; ushbu ma'lumotlar saqlanadi elementning yonida va u bilan ishlashga ta'sir qilmasdan harakat qiladi. Biroq, soddalik uchun biz ishning tavsifini qo'shimcha bilan qoldiramiz ma'lumotlar.

Birinchi navbatda quyidagi operatsiyalarni bajarish mumkin:

lNSERT (S, x) S ni o'rnatish uchun x elementini qo'shadi

MAXiMUM (S) to'plamning eng katta elementini qaytaradi;

EXTRACT-MAX (S ) elementni eng katta to'plamidan olib tashlaydi.

Imtiyozli navbat, masalan, vaqtni taqsimlovchi operatsion tizimda ishlatilishi mumkin. Bunday holda, navbatdagi vazifani bajarish tugashi bilanoq, ustuvor vazifalar ro'yxati saqlanadi eng yuqori ustuvorlikka ega ish tanlanadi (EXTRACT-MAX operatsiyasi). Ammo йo'shimcha bo`sh o'rinlar INSERT operatsiyasi yordamida navbatga qo'shiladi.

Xuddi shu tuzilmaning yana bir qo'llanilishi - bu voqealarga asoslangan modelrationing (hodisaga asoslangan simulyatsiya). Navbatdagi voqealar mavjud va ustuvor yo'nalish voqea sodir bo'lishi kerak bo'lgan vaqt bilan belgilanadi. Albatta, voqealar Turlar paydo bo'lish tartibida modellashtirilishi kerak. Tanlash keyingi tadbir EXTRACT-MIN operatsiyasi yordamida amalga oshiriladi.(buyurtma bu erda aksi), voqealarni qo'shish - INSERT operatsiyasidan foydalanish.

Keling, ustuvor navbatning bajarilishini tavsiflaylik. Biz elementni saqlaymiz siz uyum shaklidagi to'plamlarsiz. Bunday holda, maksimal element ildizda, shuning uchun MAKSIMUM ishlash vaqtni oladi (1). Maksimal pulni tortib olish uchun navbatdagi element, siz saralashda bo'lgani kabi harakat qilishingiz kerak:

Heap-Extart-Max(A)

1 if heap-size[A]<1

2 then hato: “Navbat yo`q”

3 max A[1]

4 A[1] A[heap-size[A]]

5 heap-size[A] heap-size[A]

6 Heapify(A,1)

7 return max

HEAP-INSERT protsedurasining ishlashi. Kalit qiymati 15 bo'lgan element qo'shiladi

(quyuq doira bu element uchun bo`sh joyni anglatadi).

Ishlash vaqti O (logn) (HEAPIFY protsedurasi bir marta chaqiriladi).

Biror narsani navbatga qo'shish uchun uni to`olam oxiriga qo'shish kerak (masalan varaq), so'ngra kerakli joyga "suzishga" ruxsat berish kerak:

Heap-Extart-Max(A)

1 heap-size[A] heap-size[A]+1

2 i heap-size[A]

3 while i>1 and A[Parent(i)]

4 do A[i] A[Parent(i)]

5 i Parent(i)

6 A[i] key

HEAP-INSERT protsedurasi qanday ishlashiga misol yuqoridagi rasmda ko`rsatilgan. Ishlash vaqti O(logn) dir, chunki yangi bargni ko'tarish log(n) dan oshmaydi qadamlar (indeks while tsiklining har bir takrorlanishidan keyin kamayadi kamida ikki marta).

Shunday qilib, n elementning ustuvor navbatidagi barcha operatsiyalar talab qilinadi vaqt O(log n).

Piramidali saralash

Piramidali saralash elementlarni ikkilik daraxt kabi tartibga solishga asoslangan. Ikkilik daraxt - bu har bir elementda ikkitadan ko'p bo'lmagan naslga ega bo'lgan ma'lumotlarning ierarxik tuzilishi:

1-rasm. Ikkilik daraxtga misol.

Piramida - bu har bir elementning qiymati uning har bir avlodining qiymatidan katta bo'lgan ikkilik daraxtning alohida turi. Har bir tugunning bevosita elementlariga murojat qilinmaydi, shuning uchun ba'zida chap taraf o'ng tarafdan kattaroq bo'lishi mumkin, ba'zan esa aksincha. Piramida bu to'liq daraxt bo'lib, unda yangi darajani to'ldirish avvalgi daraja to'liq to'ldirilgandan keyingina boshlanadi va bir xil darajadagi barcha tugunlar ketma-ket to'ldiriladi :

2-rasm. Piramidaning misoli.

Saralash barcha ketma-ketlikdagi elementlarni o'z ichiga olgan piramidani qurish bilan boshlanadi. Maksimal element daraxtning tepasida joylashganligi aniq, chunki uning barcha avlodlari kichikroq bo'lishi kerak. Keyin, piramidaning yuqori qismi ketma-ketlikning oxirigacha yoziladi va maksimal element olib tashlangan piramida qayta shakllanadi. Natijada, qolgan elementlarning maksimal qismi uning tepasida joylashgan bo'lib, u tegishli joyga yoziladi va protsedura piramida bo'sh bo'lguncha davom etadi.

Shunday qilib, algoritmning asosiy qismi ikki protsedura bilan amalga oshiriladi: piramidaning dastlabki qurilishi va har qadamda piramidaning shaklini o'zgartirish. Piramidani qurish uchun siz uning xususiyatidan foydalanishingiz mumkin - har bir ichki tugunning aniq ikkita avlodi bor, oldingi tugatish darajasida bitta tugun bundan mustasno. Shuning uchun, bu mumkin uchun hukmga muvofiq uchidan boshlab, tugunlari raqamlash: tugun raqami bo'lsa i , keyin biz Belg raqamlari 2 * i va 2 * i uchun +1 uning avlodlari . Natijada, piramidaning barcha tugunlari 1 va N oralig'ida noyob sonlarni oladi, bu esa piramidani ketma-ketlikda saqlashga imkon beradi :

 

3-rasm. Piramidaning ro'yxat ko'rinishi (2-rasmga qarang).

Eng katta piramida elementini tepadan olib tashlaganingizda, ildiz tuguni bo'sh qoladi. Piramida tiklangandan so'ng, unga yaqin ikki avlodning kattaroq qismi kirishi kerak , o'z navbatida uning o'rnini kim egallashini aniqlash kerak va hk. Bunda piramida iloji boricha to'liq daraxtga yaqin turishi kerak . Shu maqsadda biz eng yuqori darajadagi elementdan piramidani yuqori darajaga o'tkazib qayta shakllantira boshlaymiz. Keyin yuqoridan yuqoriga "saralash" deb nomlangan protsedurani qo'llaymiz:

 

1. 
   agar elementda farzand bo'lmasa, u holda tugatish;
   
2. 
   aks holda, biz elementning qiymatlarini va uning ikkita yaqin avlodining maksimal qiymatini almashtiramiz;
   
3. 
   o'zgartirilgan bolaga boring va 1-bosqichdan boshlab xuddi shu tartibni bajaring.
   

 

Piramidani tiklashga ushbu yondashuv uning dastlabki holatini tuzishda ham qo'llanilishi mumkin: har qanday ikkita elementni ba'zi bir bepul tugunning avlodlari deb hisoblash mumkin. Barcha elementlar "barglar" bo'lgani uchun, ketma-ketlikning ikkinchi yarmi bilan hech narsa qilishingiz shart emas. Choyshab elementlari to'plamidan boshlab, ularni umumiy katta piramida hosil bo'lguncha juft-juft qilib bog'lashingiz mumkin. N elementlar ketma-ketligiga qo'shilgan birinchi ildiz N / 2 - 1 indeksiga ega bo'ladi. Natijada, piramidani dastlabki qurish algoritmi "indekslash" protseduralarini N dan indeksli barcha elementlarga ketma-ket tatbiq etishdan iborat bo'ladi. N/ 2 - 1 dan 0 gacha.

Anjir. 4. "Elek down" protsedurasini qo'llashga misol

piramidaning o'zgartirilgan ildiziga.
// Funksiya i elementini kattalikdagi uyum ichida pastga "suzadi"

void fixHeap ( double * heap, int i, const int size)

{  

    // Hozirgi uchta elementdagi maksimal element ko'rsatkichi:

    int maxIdx = i;

// Joriy element qiymati:

double value = heap[i];

while ( true )

{

int childIdx = i * 2 + 1; // Chap bolaning ko'rsatkichi

 

     // Agar chap bola bo'lsa va u hozirgi elementdan kattaroq bo'lsa,

if ( ( childIdx < size ) && ( heap[ childIdx ] > value ) )

maxIdx = childIdx; //keyin u maksimal hisoblanadi

childIdx = i * 2 + 2; // To'g'ri bolaning ko'rsatkichi

// Agar to'g'ri bola bo'lsa va u maksimaldan kattaroq bo'lsa, if ( ( childIdx < size ) && ( heap[ childIdx ] > heap[ maxIdx ] ) )

maxIdx = childIdx; // keyin u maksimal hisoblanadi

 

        // Agar joriy element maksimal uchta bo'lsa

        // (ya'ni agar u o'z farzandlaridan kattaroq bo'lsa), unda oxir:

if ( maxIdx == i )

break;

// Joriy elementni maksimal bilan almashtiring: heap[i] = heap[ maxIdx ];

heap[ maxIdx ] = value;

// O'zgartirilgan bolaga boring i = maxIdx;

}

}

// Heap hajmi kattalikdagi massivni saralash void heapSort( double * heap, int size )

{

// Bir qatordan piramida qurish : for( int i = size / 2 - 1; i >= 0; --i )

fixHeap( heap, i, size );

// Piramida bilan saralash

while( size > 1 ) // piramidada bir nechta element mavjud bo'lsa

{

--size; // Oxirgi elementni ajratish

// Ildiz elementini va ajratib oling:

double firstElem = heap[0];

heap[0] = heap[ size ];

heap[ size ] = firstElem;

// Yangi ildiz elementini pastga siljiting:

fixHeap( heap, 0, size );

}

}