10 – mavzu. Heap tree ko’rinishidagi binar daraxtlarni qurish algoritmi va ular ustida amallar

Heap tree ko’rinishidagi binar daraxtlarni qurish algoritmi va ular ustida amallar

Heap tree ko’rinishidagi binar daraxtlarni qurish algoritmi va ular ustida amallar

1. Heap tree tuzilmasi tavsifi.
2. Heap tree ustida amal bajarish algoritmlari.
3. Heap treeni tashkil etish usullari va samaradorligi.
1. Heap tree tuzilmasi tavsifi
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.
Bu daraxtni heap tree ko’rinishida qayta tashkil etish uchun uzunligi n ga teng heap massivini quyidagi shartlarga asoslanib tashkil etamiz:
heap[i] ≥ heap[2·i], for 0 ≤ i<
va
heap[i] ≥ heap[2·i + 1], for 0 ≤ i<
heap tree elementlari tartiblanmagan hisoblanadi.
Boshqacha qilib aytadigan bo’lsak, sonlar ketma-ketligidan heap treeni qurish uchun

• 1-elementni daraxt ildizi qilib olamiz.
• Har qanday i-element uchun quyidagi o’rinli:
• Uning chap o’g’il tuguni 2*i indeksda
• O’ng o’g’il tuguni esa 2*i+1 indeksda
• Uning ota tuguni i/2 indeksda bo’ladi.

Heap tree
Ya’ni 1-elementni ildiz qilib olgach, qolgan elementlarni chapdan o’ngga qarab daraxtni to’ldirib ketiladi. Xar bir ildizda faqat ikkita o’g’il tugun chiqishi kerak. Agar shunday tartibda elementlar joylashtirilib chiqadigan bo’lsa, xar bir a[i]-o’rinda turgan ota tugunning chap tomoniga a[2*i]-element va o’ng tomoniga esa a[2*i+1]-element joylashadi. Quyida bir xil sonlardan turlicha heap tree xisol qilinganligi keltirilgan:
bir xil sonlardan tashkil topgan heap tree tuzilmalari
Heap tree nimaga kerak?
Heap tree prioritetli navbatni ifodalashda juda qo’l keladi. Eng kerakli element tuzilma eng yuqorisida joylashadi. Agar u o’chirilsa, elementlar qayta joylashtirilishi zarur. Bu tuzilma graflarda eng qisqa masofani aniqlash masalasini echish Dijkstra algoritmini samaradorligini oshirishda prioritetli navbatlardan foydalanilganda qo’l keladi. Bundan tashqari heap tree - samaradorligi O(nlogn) bo’lgan piramida saralash algoritmida ham qo’llaniladi.