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

Heap tree ustida amal bajarish algoritmlari
Heap tree ustida bajariladigan amallar:

• Element qo’shish
• Element o’chirish

Min-heapga yangi element kiritish algoritmi:

• Yangi elementni massivning navbatdagi indeksiga joylash;
• Yangi elementni ota tugun bilan solishtiring, agar yangi element otasidan kichik bo’lsa, ularni o’rin almashtiring;
• Bu jarayon takrorlanadi toki:
• Yoki yangi elementning otasi kichik yoki teng bo’lguncha;
• 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 o’chirish algoritmi:

• O’chiriladigan element o’rniga daraxtdagi eng quyi darajada turgan eng o’ngdagi, ya’ni oxirgi element joylashtiriladi.
• O’rni o’zgargan shu element ikkita o’g’il tugunlari bilan solishtiriladi va agar ulardan katta bo’sa, kichik o’g’il tugunl bilan almashtiriladi.
• O’rinlashtirishda qatnashgan element ta’sir qiladigan qism daraxtlar tekshirib chiqiladi, buning uchun oxirgi ikkita amal takrorlanadi.

Masalan, 3-rasmdagi heap treedan 5 ni o’chiramiz. Quyidagi heap tree xosil bo’ladi.
Agar bundan 14 ni o’chirsak, quyidagi ko’rinishga keladi:
Heap tree tuzilmasi bilan ishlash samaradorligi:
Agar tuzilmada N ta element mavjud bo’lsa, undagi bosqichlar soni log2(N+1) ta teng.

• Yangi element kiritishda 1ta boqsichda 1ta elementdan k’op bo’lmagan o’rinlashtirish bajarilishi sababli kiritish samaradorligi O(lon(n)) ga teng.

Element o’chirishda ham xar bir bosqichda faqat 1 ta o’rinlashtirish bajarilishi mumkinligi sababli o’chirish samaradorligi O(log(n)) gat eng.

Heap treeni tashkil etish usullari va samaradorligi
Heap treeni dasturda massiv ko’rinishida ifodalash mumkin, ya’ni barcha heap tuzilmalarni massiv ko’rinishida ifodalash mumkin, lekin barcha massivlar heap bo’lmaydi. Berilgan massiv elementlarini shunday joylash kerakki, natija heap treeni ifodalasin. Buning bir necha usullari mavjud. Eng soddasi bo’sh heapga ketma-ket elementlarni joylash bilan amalga oshiriladi. Bu “tepadan-pastga” usuli (ya’ni elementlar heapga yuqorida keltirilgan yangi element qo’shish algoritmi bilan kiritiladi) bo’lib, Jogn Williams tomonidan taklif etilgan. Quyida rasmda “tepadan-pastga” algoritmi ifodalangan va dasturi keltirilgan.
10.6-rasm. Heap treeni “tepadan-pastga” usuli bilan tashkil etish.
Bu algoritm samaradorligini eng yomon holatda tekshiradigan bo’lsak, unga kiritilgan xar bir element ildizgacha yuqoriga xarakat qilishi kerak. Bunda k ta elementdan iborat bo’lgan heapda yangi kiritilgan element yuqoriga xarakat qilishi uchun [lg k] ta o’rin almashtirishlar amalga oshirilishi kerak. Agar n ta yangi element kiritilsa, eng yomon xolatda algoritm bajarilishi quyidagicha o’rinlashtirishlar bajariladi, solishtirishlar ham xuddi shunday.
Robert Floyd tomonidan taklif etilgan boshqa bir algoritmda heap tree “pastdan-yuqoriga” usuli yordamida amalga oshiriladi. Bunda kichik heap qismlar yaratiladi va davriy ravishda kattaroq heaplarga birlashtiriladi. (10.7-rasm)
(quyidagi listingda keltirilgan moveDown() funksiyasi ildizdagi elementlarni quyiga xarakat qildiradi.)
FloydAlgorithm(data[])
for i = index of the last nonleaf down to 0
restore the heap property for the tree whose root is data[i] by calling
moveDown(data,i,n-1);
10.7-rasm. Array[2 8 6 1 10 15 3 12 11] massivni “pastdan-yuqoriga” usuli bilan heap treega aylantirish.
Bunda elementlarni tekshirish data[n/2-1] barg tugun bo’lmagan elementdan boshlaymiz. Agar u o’g’il tugunlarining birontasidan kichik bo’lsa, katta qiymatli o’g’il element bilan almashtiriladi va jarayon yuqoridagi rasmdagi kabi davom ettiriladi. Bu usulda qachonki yangi element tahlil qilinayotganda uning qism daraxti allaqachon heap bo’ladi. 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 bo’lgan eng quyi bosqishga ko’chiradi, bunda barg tugunlar bosqichiga yetib kelguncha xar bir bosqichda (n+1)/4 ta o’rinlashtirishlarni amalga oshiradi.
Qisqasi, bu usul samaradorligi O(n) gat eng. Shu sababli eng o’g’ir holatda Williamning usuli Floydning usulidan samaraliroq hisoblanadi. O’rta holatda esa ikkala algoritm ham deyarli bir xil.