Heap tree korinishidagi binar daraxtlarni qurish algoritmi va ular ustida amallar



Yüklə 4,75 Kb.
tarix07.01.2024
ölçüsü4,75 Kb.
#212133
Heap tree korinishidagi binar daraxtlarni qurish algoritmi va ul-fayllar.org


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.




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
Yüklə 4,75 Kb.

Dostları ilə paylaş:




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin