Мундарижа Кириш

Якунловчи алгоритм
Барча ёзилган қисмларни бирга йиғиб ва пирамидадан элементларни рўйхатга кўчириш бўйича амалларни қўшиб якунлочи алгоритмни ҳосил қиламиз
for i=N/2 down to 1 do
FixHeap( list, i, list[i], N)
end for
for i=N down to 2 do
max=list[1]
FixHeap(list, i, list[i], i-1)
list [i] =max
end for
Энг ёмон ҳол таҳлили
Таҳлилни FixHeap алгоритми таҳлилидан бошлаймиз, чунки алгоритмнинг қолган қисми унинг асосига қурилади. Пирамиданинг ҳар бир даражасида алгоритм икки бевосита авлодни солиштиради, яна улардан каттасини ва калитни. Бу шуни билдирадики, D чуқурликка эга пирамиданинг солиштиришлари сони 2D дан ошмайди.
Пирамидани қуриш босқичида ҳар бир охиридан иккинчи даража учун биз дастлаб FixHeap процедурани чақирамиз. Кейин у пастдан учинчи даражанинг ҳар бир тугуни учун чақирилади, яъни 2 чуқурликка эга пирамида қурилади. Охирги ўтишда илдиз даражада чуқурликка эга пирамида қурилади. Бизга фақат ҳар бир ўтишда қанча тугунлар сони учун FixHeap процедураси чақирилишини ҳисоблаш қолди. Илдиз даражада тугун битта, иккинчи даражада эса унинг икки ўғли жойлашган. Кейинги даража тугунлари сони тўртдан ошмайди, кейингиси эса - саккиздан. Ушбу натижаларни бирлаштириб қуйидаги формулага келамиз

(1.17) ва (1.19) тенгликлардан

D га — ни қўйиб, ҳосил қиламиз

Шунинг учун пирамидани қуриш босқичи рўйхат элементлари сони бўйича чизиқли қийинликка эга.
Энди алгоритмнинг асосий циклига қараймиз. Бу циклда биз пирамидадан битта элементни олиб ташлаймиз, сўнгра FixHeap процедурани чақирамиз. Цикл пирамидада элемент қолмагунча давом эттирилади. Ҳар бир ўтишда элементалр сони 1 га камаяди. Пирамиданинг чуқурлиги қандай ўзгаради? Юқорида айтганимиздек, бутун пирамиданинг чуқурлиги га тенг, шунинг учун агар пирамидада К тугунлар қолган бўлса, у ҳолда унинг чуқурлиги га тенг, солиштиришлар сони эса икки баравар катта. Буни шуни билдирадики, энг ёмон ҳолатда циклда

амаллар бажарилади. Аммо бундай йиғинди учун бизда стандарт ифода йўқ.
Бу тўсқинликни қандай бартараф қилишни қараймиз. k = 1 да га эгамиз. k 2 ёки 3 га тенг бўлганда га эгамиз. Ва ҳакозо, k 4 дан 7 гача ва k 8 дан 15 гача. Бу даражада элементлар мавжуд.
Шунинг учун охирги тенгликни қуйидаги шаклда ёзиш мумкин
бунда
(1.19) тенгликдан

энди ни қўйиб ҳосил қиламиз

Якуний натижани олиш учун қуриш процедураси ва цикл қийинликларини қўшиш қолди. Натижада қуйидагига эга бўламиз