Ma’lumotlar tuzilmasi va algoritmlar

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 bo’lmagan 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.