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

2.2.4. Пирамида усули билан саралаш алгоритми

Пирамидали саралашнинг асосида пирамида деб аталувчи бинар дарахтнинг махсус тури ётади; бундай дарахтдаги исталган қисм дарахт илдизининг қиймати унинг авлодалари қийматидан катта бўлади. Бевосита ҳар бир тугун авлодлари тартибланмаган, шунинг учун баъзида чап авлод ўнгидан кичик бўлади, баъсида бунинг тескариси бўлади. Пирамида ўзида янги даражани тўлдириш фақат олдинги даража тўлиқлигича тўлдирилгач бошланадиган ва бир даражада тугунлар чапдан ўнгга тўлдириладиган тўлиқ дарахтни намоён қилади.

Саралаш пирамидани қуришдан бошланади. Бунда максимал элемент дарахт учида жойлашади, чунки унинг авлодлари кичик бўлиши керак. Кейин илдизга рўйхатнинг охирги элементи ёзилади, ўчирилган максимал элементли пирамида эса қайта тузилади. Натижада илдизда катталиги бўйича иккинчи элемент пайдо бўлади, у рўйхатга кўчирилади ва бу жараён барча элементлар рўйхатга қайтгунча давом эттирилади. Мос келувчи алгоритм қуйидагича:

пирамидани тузиш

for i=1 to N do

пирамида илдизини рўйхатга кўчириш

пирамидани қайта тузиш

end for

Бу алгоритмдаги айрим жиҳатларни аниқлаштириш керак. Дастлаб пирамидани тузиш ва қайта тузиш қанақа жараёндан иборатлигини аниқлашимиз керак: бу алгоритм самарадорлигига таъсир кўрсатади.

Бизни алгоритм иши қизиқтиради. Бинар дарахтни қуришга кетадиган қўшимча харажатлар рўйхат ўсиши билан ўсади. Аммо банд рўйхат ўрнидан фойдаланиш мумкин. рўйхатни пирамидага «қайта қуриш» мумкин, агар ҳар бир ички тугунда икки бевосита авлод бўлса, мустасно ҳолда, охиргидан олдинги даражада битта тугунда битта бўлади. Кейинги кўриниш талаб қилинган пирамидани шакллантиришга имкон беради. i рақамли элементнинг бевосита авлодларини 2i ва 2i + 1 ўринларга ёзамиз. Сезамизки, натижада барча авлодлар ҳолати турлича бўлади. Биламизки, агар 2i > N бўлса, у ҳолда i тугун япроқ бўлади, агар 2i = N бўлса, у ҳолда i тугунда битта авлод бўлади. 3.3-расмда пирамида ва унинг рўйхат кўриниши тасвирланган.



3.3-расм. Пирамида ва унинг рўйхат кўриниши

Пирамидани қайта шакллантириш

Энг катта элементни илдиздан рўйхатга кўчиришда илдиз тугун бўш қолади. Биз биламизки унга икки бевосита авлодлардан каттаси тушади ва ким унинг ўрнига тушишини қарашимиз керак ва ҳ.к. бунда пирамида иложи борича тўлиқ дарахтга яқинроқ ҳолда қолиши керак. пирамидани қайта шакллантиришни унинг пастки даражадаги энг ўнгдаги элементидан бошлаймиз. Натижада дарахтнинг пастки даражасидаги тугунлар тенгликда йўқотилади. Агар бунга эътибор берилмаса ва барча катта элементлар пирамиданинг бир томонига ўтиб қолади ва алгоритм самарадорлиги пасаяди. Натижада мана бу алгоритм ҳосил бўлади:

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

Якунловчи алгоритм

Барча ёзилган қисмларни бирга йиғиб ва пирамидадан элементларни рўйхатга кўчириш бўйича амалларни қўшиб якунлочи алгоритмни ҳосил қиламиз

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) тенгликлардан