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

Пирамидани қайта шакллантириш
Энг катта элементни илдиздан рўйхатга кўчиришда илдиз тугун бўш қолади. Биз биламизки унга икки бевосита авлодлардан каттаси тушади ва ким унинг ўрнига тушишини қарашимиз керак ва ҳ.к. бунда пирамида иложи борича тўлиқ дарахтга яқинроқ ҳолда қолиши керак. пирамидани қайта шакллантиришни унинг пастки даражадаги энг ўнгдаги элементидан бошлаймиз. Натижада дарахтнинг пастки даражасидаги тугунлар тенгликда йўқотилади. Агар бунга эътибор берилмаса ва барча катта элементлар пирамиданинг бир томонига ўтиб қолади ва алгоритм самарадорлиги пасаяди. Натижада мана бу алгоритм ҳосил бўлади:
FixHeap(list,root,key,bound)
list сараланадиган рўйхат / пирамида
root пирамиданинг илдизи рақами
key пирамидага қўйиладиган калит қиймат
bound пирамидадаги чап чегара(рақам)
vacant = root
while 2*vacant <= bound do
large-Child = 2*vacant
// икки бевосита авлоддан каттасини топиш
if (largerChild
list[largerChild+1]) then
largerChild=largerChild+1
end if


// калит жорий авлоддан юқори жойлашганми?
if key>list[largerChild] then
// ҳа, цикл тугатилади
break
else
// йўқ, бевосита авлодлардан каттасини кўтариш керак
list[vacant]=list[largerChild]
vacant=largerChild
end if
end while
list[vacant]=key
Ушбу алгоритмнинг параметрларги қараб савол туғилиши мумкинки, ўзгарувчи root нима учун керак. Ҳақиқатан, процедура рекурсив эмас, пирамида илдизи доим биринчи бўлиши керак. Кўришимиз мумкинки, бу қўшимча параметр пирамидани пастдан юқорига қуришга имкон беради. Чап чегара қиймати элементларни рўйхатга кўчиришда пирамида сиқилганлиги туфайли киритилган.
Пирамидани қуриш
Бизнинг FixHeap функцияга ёндашишимиз пирамиданинг бошланғич ҳолатини шакллантиришга имкон беради. Исталган икки қийматни эркин тугуннинг япроқлари деб ҳисоблаш мумкин. Чунки барча элементлар япроқ ҳисобланади ва рўйхатнинг иккинчи ярми билан нимадир қилишнинг аҳамияти йўқ. Биз япроқлардан оддий кичик пирамидалар қилишимиз мумкин, сўнгра қадамба-қадам уларни барчаси бир рўйхатга тушмагунча тўплаймиз. Қуйидаги цикл бу жараённи амалга оширишга имкон беради:
for i=N/2 down to 1 do
FixHeap(list, i, list[i], N)
end for