Vyberanie prvku s najväčšou prioritou
Vieme už, že najväčší prvok sa nachádza v koreni. Keď ho však chceme z haldy vybrať, potrebujeme nový koreň. Toto sa dá riešiť veľa spôsobmi, my si ukážeme jeden z nich. Budeme postupovať nasledovne:
- Vyberieme prvok z koreňa a odložíme si ho nabok. Toto je prvok, ktorý chceme vrátiť ako výstup z našej funkcie, najskôr ale musíme po sebe upratať.
- Strom má naďalej ten istý tvar ako mal doteraz, len v koreni je prázdne miesto.
- Vyberieme si ľubovoľný jeden list, ktorý sa nám páči. Ten odstránime (čím zmeníme tvar stromu). Hodnotu, ktorá bola doteraz uložená v odstránenom liste, umiestnime na voľné miesto do koreňa.
- Dostali sme teraz korektnú haldu? Zrejme nie. Ale ak nie, jediné miesto, kde môže byť porušená podmienka haldy, je samotný koreň. Toto opravíme (spôsobom, ktorý si popíšeme nižšie).
Na opravu haldy použijeme proces veľmi podobný tomu, ktorý sme používali pri vkladaní, len pôjdeme opačným smerom. Tomuto procesu sa teda bude hovoriť bublanie dodola.
Máme teda nejaký vrchol $v$, ktorý nespĺňa podmienku haldy. (Na začiatku je to koreň.) To znamená, že v aspoň jednom z jeho synov je väčší prvok ako vo $v$. Nech $u$ je ten syn, v ktorom je najväčší prvok zo všetkých synov vrcholu $v$. Vymeňme hodnoty v $u$ a $v$.
Čo sme tým dosiahli? Zjavne po tejto výmene už platí podmienka haldy pre vrchol $v$. (Nová hodnota vo $v$ je väčšia aj od tej, ktorá tam bola doteraz, a je väčšia alebo rovná od hodnôt v ostatných synoch vrcholu $v$.) Mohli sme ju však pokaziť vo vrchole $u$, do ktorého sme presunuli menšiu hodnotu. Spravíme teda to isté ako pri bublaní dohora -- znova zopakujeme ten istý postup, len s vrcholom $u$. Takto hodnotu z koreňa posúvame hlbšie a hlbšie dolu stromom, až kým sa nedostane na úroveň, kam patrí -- čiže buď do listu, alebo do nejakého vrcholu, pod ktorým už sú samé prvky s ešte menšou prioritou ako ten, ktorý práve buble dodola.
Cvičenie 2
Predstavme si, že vykonávame vyššie popísaný algoritmus: presunuli sme nejaký prvok z listu do koreňa a potom sme ho trikrát "prebublali" hlbšie. Teraz sa tento prvok nachádza vo vrchole $x$. Prezrieme všetkých synov vrcholu $x$ a nájdeme syna $y$, ktorý obsahuje najväčší prvok spomedzi nich. Ten je väčší aj od toho nášho, vymeníme ich teda medzi sebou. Ako sme spomenuli vyššie, touto výmenou sme mohli pokaziť podmienku haldy vo vrchole $y$, do ktorého sme presunuli menší prvok ako mal doteraz.
Všimnime si ale, že do vrcholu $x$ sme práve presunuli väčší prvok ako tam bol doteraz. Nemohli sme takto pokaziť podmienku haldy aj na hrane z vrcholu $x$ do jeho otca?
Cvičenie 2 - riešenie
Počas prvých troch krokov nášho algoritmu sme prvok, ktorý je teraz vo vrchole $x$, postupne vymenili s prvkami $p_1, p_2$ a $p_3$. Tieto boli pôvodne na nejakej ceste dole haldou, preto platilo $p_1 \geq p_2 \geq p_3$. Priamo pod $p_3$ bol doteraz prvok, ktorý je vo vrchole $y$. No a práve ten istý prvok teraz nasledujúcou výmenou vrátime späť pod $p_3$. Preto pri výmene prvkov vo vrcholoch $x$ a $y$ nad sebou podmienku haldy nikdy neporušíme.