Mavzu : Heap tree tuzilmasi tavsifi. Heap
tree ustida amal bajarish
algoritmlari. Heap treeni tashkil etish usullari va samaradorligi.
Reja :
1 . Heap tree tuzilmasi
2, Heap tree ustida amal bajarish algoritmlari
3. Heap treeni tashkil etish usullari va samaradorligi
4. mavzuga oid misollar
5. xulosa
6.foydalanilgan adabiyotlar
Heap tree so’zi inglizchadan olingan bo’lib, ikkilik uyurma daraxti degan
ma’noni anglatadi va binar daraxtning bir turi bo’lib,
binar daraxtdan
quyidagi ikkita xususiyati bilan ajralib turadi.
Har bir tugun qiymati uning o’g’il tugunlari qiymatidan katta yoki
teng (yoki kichik yoki teng bo’lishi ham mumkin);
Daraxt ideal muvozanatlangan, yoki daraxt barg tugunlari chapdan
o’ngga qarab to’ldiriladi.
Agar xar bir tugun o’g’il tugunlatdan katta yoki teng bo‘lsa, bu
uyurma daraxtiga
max heap, aks holda ya’ni ota tugun
farzandlardan kichik yoki teng bo’lsa,
min heap deyiladi. Bu
degani, max heap da maksimal element daraxt ildizida joylashadi,
min heapda esa daraxtning ildizida minimal element joylashadi.
Heap tree (a) va heap tree bo’lmagan daraxtlar Bu yerda rasmdagi
a) heap tree va b),c) lar esa heap tree emas. Chunki b va c rasmda
heap treening birinchi va ikkinchi xususiyatlari buzilgan mos
ravishda. Qizig’I shuki, heap tree massiv yordamida yasalishi
mumkin. Masalan, data[] = {2 8 6 1 10 15 3 12 11}
massiv
berilgan bo’lsin. Undan yuqoridan pastga va chapdan o’ngga
elementlarni joylab daraxtni (heap tree bo’lmagan) xosil qilamiz.
Bunday daraxtlarda bosqichlar soni O(lgn) gat eng.
heaplar ko'pincha e'tibordan chetda qoladigan ma'lumotlar tuzilmasi
bo'lib, lekin intervyu bilan bog'liq muammolar tez-tez
uchraydi.
heaplar - bu ikkita xususiyatni qondiradigan maxsus daraxtga
asoslangan ma'lumotlar tuzilmalari:
1.
Barcha tugunlar heap turiga qarab ma'lum bir tarzda tartibga
solinadi. Ikki xil to'plar mavjud: minimal to'plar va maksimal
to'plar.
