Heap tree korinishidagi binar daraxtlarni qurish algoritmi va ular ustida amallar

Heap tree korinishidagi binar daraxtlarni qurish algoritmi va ular ustida amallar

xmlns:w="urn:schemas-microsoft-com:office:word"

xmlns="http://www.w3.org/TR/REC-html40">
10 rinishidagi binar daraxtlarni qurish algoritmi va ular ustida amallar

Heap tree korinishidagi 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 solib, ikkilik uyurma daraxti degan malib, binar daraxtdan quyidagi ikkita xususiyati bilan ajralib turadi.

• 
  Har bir tugun qiymati uning oil tugunlari qiymatidan katta yoki teng (yoki kichik yoki teng bongga qarab toglsa, bu uyurma daraxtiga max heap, aks holda yalsa, 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 boI shuki, heap tree massiv yordamida yasalishi mumkin. Masalan, data[] = {2 8 6 1 10 15 3 12 11} massiv berilgan bongga elementlarni joylab daraxtni (heap tree borinishida qayta tashkil etish uchun uzunligi n ga teng heap massivini quyidagi shartlarga asoslanib tashkil etamiz:

heap[i] i<
va
heap[i] i<
heap tree elementlari tartiblanmagan hisoblanadi.
Boshqacha qilib aytadigan borinli:

• 
  Uning chap oil tuguni 2*i indeksda
  
• 
  Ogladi.
  

Heap tree

Yangga qarab daraxtni toglsa, xar bir a[i]-ong 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 qochirilsa, elementlar qayta joylashtirilishi zarur. Bu tuzilma graflarda eng qisqa masofani aniqlash masalasini echish Dijkstra algoritmini samaradorligini oshirishda prioritetli navbatlardan foydalanilganda qolgan piramida saralash algoritmida ham qoshish

• 
  Element olsa, ularni olguncha;
  

• 
  Yoki yangi element ildizga kelguncha (massivda 0 indeksga kelguncha).
  

Min-heapga yangi 43 sonini kiritamiz

Min-heapga 18 ni kiritamiz.
Min-heapga 2 ni kiritamiz
Min-heap treedan elementni ochiriladigan element ongdagi, yarni ogsa, kichik oil tugunl bilan almashtiriladi.

• 
  Osir qiladigan qism daraxtlar tekshirib chiqiladi, buning uchun oxirgi ikkita amal takrorlanadi.
  

Masalan, 3-rasmdagi heap treedan 5 ni oladi.
Agar bundan 14 ni orinishga keladi:
Heap tree tuzilmasi bilan ishlash samaradorligi:
Agar tuzilmada N ta element mavjud boop borinlashtirish bajarilishi sababli kiritish samaradorligi O(lon(n)) ga teng.
Element orinlashtirish bajarilishi mumkinligi sababli orinishida ifodalash mumkin, yarinishida ifodalash mumkin, lekin barcha massivlar heap bosh heapga ketma-ket elementlarni joylash bilan amalga oshiriladi. Bu usuli (yashish algoritmi bilan kiritiladi) botepadan-pastgatepadan-pastgalsak, unga kiritilgan xar bir element ildizgacha yuqoriga xarakat qilishi kerak. Bunda k ta elementdan iborat borin almashtirishlar amalga oshirilishi kerak. Agar n ta yangi element kiritilsa, eng yomon xolatda algoritm bajarilishi quyidagicha opastdan-yuqorigapastdan-yuqorigalmagan elementdan boshlaymiz. Agar u oil tugunlarining birontasidan kichik bogladi. Shunday qilib, heap tree pastdan yuqoriga qarab shakllantiriladi.
Heapni bunday taskil qilishda, moveDown() funksiyasi (n+1)/2 marta chaqiriladi, xar bir barg bulmagan tugun uchun. Eng yomon holatda moveDown() elementni (n+1)/4 ta elementdan iborat bochiradi, bunda barg tugunlar bosqichiga yetib kelguncha xar bir bosqichda (n+1)/4 ta ogrta holatda esa ikkala algoritm ham deyarli bir xil.
http://hozir.org
http://fayllar.org