Ustivor navbat - bu yozuvlar bir-biri bilan chiziqli taqqoslanadigan
kalitlarga (masalan, raqamlar) ega bo'lgan va ikkita amalni realizatsiya
qiladigan axborot tizimidir. Bu ikki amal tizimga tasodifiy yozuvni
kiritish va yozuv tizimidan eng kichigi bilan tanlov kalit.
Dasturiy ta'minot tizimlarida ustivor navbatlar juda keng tarqalgan
va dasturlarning ishlashi to'gʻridan-to'gʻri ularni amalga oshirish
samaradorligiga bogʻliq.
Ustivorda navbatda qoʻllab-quvvatlanadigan amallar quyidagilar
hisoblanadi:
1)
Insert - navbatga element qo'shish
2)
Max - ustivorligi yuqori bo'lgan elementni qaytaradi
3)
ExtractMax - navbatdagi eng ustivor elementni olib tashlaydi
4)
IncreaseKey - berilgan elementning ustivor qiymatini o'zgartiradi
5)
Merge - ikkita navbatni bittaga birlashtiradi
11.1. Binar uyum (kucha) - piramida (binary heap) Binar
uyum
(binary
heap)
bu
quyidagi
shartlarni
qanoatlantiradigan binar daraxtdir:
- Har qanday uchning ustivorligi, uning avlodlarining ustivorligidan
kichik emas.
- Daraxt to'liq ikkilik daraxt boʻlishi uchun (complete binary tree) -
barcha darajalar chapdan o'ngga to'ldiriladi (oxirgisi bundan mustasno
boʻlishi mumkin).
142
50-rasm. Binar uyum (kucha) Massivlar orqali binar uyum (kucha) ni realizatsiya qilish
16 14 10 8
7
9
3
2
4
1
O‟smaydigan piramida max-heap
Har qanday uchning ustuvorligi
avlodlarning ustuvorligidan kichik
emas
Kamaymaydigan piramida min-heap
Har qanday uchning ustuvorligi
avlodlarning ustuvorligidan katta
emas
H[1..10] ustuvorliklar (kalitlar) massivi max-heap (10 ta element)
143
Daraxtning ildizi H [1] yacheykada saqlanadi - bu maksimal element;
tugunning ajdod indeksi:
𝑃 𝑡
(
)= [
/ 2];
Chap avlod tugun indeksi:
𝑡
;
Oʻng avlod tugun indeksi: Right(i) =
𝑃 𝑡
.
struct heapnode {
int key; /* kalit */
char *value; /* qiymat*/
};
struct heap {
int maxsize; /* massiv oʻlchami */
int nnodes; /* Kalitlar soni */
struct heapnode *nodes; /* Nodes: [0..maxsize] */
}
