O’zbekiston respublikasi oliy va o’rta maxsus ta’lim vazirligi toshkent axborot texnologiyalari universiteti

14 – mavzu. Heap tree tuzilmasi, uni qurish va
ustida amal bajarish algoritmlari


Reja

1. 
   Heap tree tuzilmasi tavsifi.
   
2. 
   Heap tree ustida amal bajarish algoritmlari.
   
3. 
   Heap treeni tashkil etish usullari va samaradorligi.
   

Kalit so’zlar: heap tree, element, algoritm, binar daraxt.


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.

13.1-rasm. 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.

13.2-rasm. Massivdan daraxt xosil qilish
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.
    

13.3-rasm. 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:

13.4 – bir xil sonlardan tashkil topgan heap tree tuzilmalari

13.5. Heap treeni to’g’ri va noto’g’ri tashkil etilganligi.

Bu min-heapmi yoki yo’q?

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.