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

Heap tree tuzilmasi bilan ishlash samaradorligi:

Agar tuzilmada N ta element mavjud bo’lsa, undagi bosqichlar soni log₂(N+1) ta teng.

• 
  Yangi element kiritishda 1ta boqsichda 1ta elementdan k’op bo’lmagan o’rinlashtirish bajarilishi sababli kiritish samaradorligi O(lon(n)) gat eng.
  
• 
  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.

13.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. (11.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);

13.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.