Halda

V tomto texte si budeme rozprávať o haldách: jednoduchých stromových dátových štruktúrach, ktoré nám umožňujú udržiavať si údaje "tak trochu usporiadané". Ukážeme si, ako sa to robí a na čo je to dobré.

Počas vysvetľovania sa v tomto texte budú zjavovať obrázky rôznych stromov. Nebojte sa ich. Nebude ich treba implementovať. Keď sa úspešne dostaneme až na koniec našich úvah, ukáže sa, že nám bude stačiť jedno obyčajné pole.

Prioritná fronta

Naším hlavným cieľom v tomto článku bude efektívna implementácia takzvanej prioritnej fronty. Toto je dátová štruktúra, ktorá vie efektívne robiť dve operácie:

• push(prvok,priorita): vlož nový prvok a nastav mu konkrétnu prioritu
• pop(): vyber prvok, ktorý má spomedzi všetkých aktuálne uložených prvkov najväčšiu prioritu

Prioritnú frontu si teda vieme predstaviť ako čakáreň na pohotovosti. Postupne nám prichádzajú pacienti, každý s inou prioritou -- niekto je na tom lepšie, niekto horšie. No a vždy, keď sa ordinácia uvoľní, ošetrujúci lekár do nej zoberie pacienta s najväčšou prioritou, teda toho, kto najakútnejšie potrebuje ošetrenie.

Iné implementácie prioritnej fronty

Technický detail o prvkoch a prioritách

V nasledujúcom texte si pre jednoduchosť budeme zaoberať haldami, v ktorých sú uložené obyčajné prirodzené čísla. Pri skutočnom použití haldy tieto čísla predstavujú priority prvkov uložených v halde. Ak teda napríklad na nižšie uvedenom obrázku vidíte krúžok a v ňom číslo 47, toto číslo môže napríklad predstavovať celý záznam o pacientovi, ktorého priorita v čakárni je 47.

Podobne, keď budeme písať "prvok X je väčší ako prvok Y", myslíme tým, že X má väčšiu prioritu.

Všeobecná maximová halda

Maximová halda je zakorenený strom, v ktorom platí: prvok uložený v hociktorom vrchole je väčší alebo rovný ako každý z prvkov uložených v synoch daného vrcholu. Túto vlastnosť budeme volať podmienka haldy

(Analogicky existuje aj minimová halda, kde uvažujeme opačnú podmienku -- prvok uložený v hociktorom vrchole musí byť menší alebo rovný ako každý z prvkov uložených v jeho synoch.)

Všimnite si, že z podmienky haldy vyplýva, že pre ľubovoľný vrchol $v$ haldy platí, že hodnota v ňom je najväčšia z hodnôt v celom podstrome s koreňom $v$. (Totiž hodnota vo $v$ je väčšia alebo rovná ako hodnoty v jeho synoch, tie sú zase väčšie alebo rovné ako hodnoty v ich synoch, a tak ďalej.)

V koreni haldy je teda nutne vždy uložený najväčší zo všetkých prvkov v halde.

Vkladanie prvku do haldy

Predstavme si, že už odniekiaľ máme maximovú haldu: niekto už vybral konkrétny tvar stromu a rozmiestnil prvky do jeho vrcholov tak, aby spĺňali podmienku haldy. Ako vieme do takejto haldy pridať ďalší prvok?

Spravíme to veľmi jednoducho. Začneme tým, že nový prvok pridáme ako nový list kamkoľvek do stromu. Označme nový vrchol $v$ a jeho otca $u$. Vieme, že doteraz každý vrchol spĺňal podmienku haldy. Keď sme do stromu pridali vrchol $v$, jediné miesto, kde sme ju mohli pokaziť, je vrchol $u$, presnejšie hrana z $u$ do $v$.

Ak je táto hrana v poriadku (čiže ak je prvok vo vrchole $u$ väčší alebo rovný od nového prvku vo vrchole $v$), máme opäť haldu a sme hotoví. V opačnom prípade treba haldu upraviť.

Počas úpravy nebudeme vôbec meniť tvar našej haldy, len šikovne povymieňame prvky medzi sebou. Začneme v práve pridanom liste. Ako opraviť podmienku haldy pre hranu $uv$? Jednoducho: vymeníme prvky uložené v týchto dvoch vrcholoch.

V tomto okamihu už máme podmienku haldy určite splnenú vo vrchole $u$. Tento vrchol mohol mať pod sebou aj iných synov okrem $v$, no keďže pôvodná halda bola v poriadku a výmenou sme do vrcholu $u$ presunuli prvok väčší ako ten, čo tam bol doteraz, podmienku haldy sme tým nemali ako pokaziť.

Opäť teda existuje jediné miesto v celom strome, kde môže ešte byť pokazená podmienka haldy. Týmto miestom je hrana z vrcholu $u$ do jeho otca. A toto je presne tá istá situácia, v ktorej sme boli na začiatku (len sme v strome o úroveň vyššie). Opakujeme teda ten istý postup.

V najhoršom prípade tento postup skončí tým, že sa dostaneme až do koreňa celej haldy. Ten už nad sebou nič ďalšie nemá, takže v tej chvíli už je všade splnená podmienka haldy a môžeme skončiť.

Postup, ktorý sme si práve popísali, sa zvykne nazývať bublanie dohora, lebo sa naň dá dívať tak, že naposledy pridaný prvok postupne stúpa haldou až kým nepríde na miesto, kam patrí.

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:

1. 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ť.
2. Strom má naďalej ten istý tvar ako mal doteraz, len v koreni je prázdne miesto.
3. 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.
4. 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.

Zamyslenie nad časovou zložitosťou

Zlé tvary haldy

Jeden možný dobrý tvar haldy

Z odhadov časovej zložitosti je jasné, ako by mala dobrá halda vyzerať: mala by mať malú hĺbku a mala by zároveň mať malé stupne vrcholov. Existujú rôzne typy stromov, ktoré toto spĺňajú. Asi najjednoduchším typom sú takzvané takmer úplné binárne stromy. Pripomeňme si, že v binárnom strome môže každý vrchol mať nanajvýš dvoch synov -- jedného ľavého a jedného pravého. A tiež si pripomeňme, že hĺbka vrcholu je definovaná ako počet hrán na ceste z neho do koreňa. Binárny strom môžeme rozdeliť na úrovne. Úroveň $k$ tvoria všetky vrcholy, ktoré majú hĺbku $k$. Všimnime si, že na úrovni $k$ môžeme mať nanajvýš $2^k$ vrcholov. (Na úrovni 0 je len koreň, ten má nanajvýš 2 synov ktorí tvoria úroveň 1, každý z nich má nanajvýš 2 synov ktorí spolu tvoria úroveň 2, atď.) Binárny strom voláme úplný, ak je každá jeho úroveň buď prázdna alebo úplne plná -- inými slovami, ak má každý vrchol v každej úrovni okrem poslednej práve dvoch synov. Úplný binárny strom hĺbky $k$ má teda presne $1+2^1+\cdots+2^{k-1}+2^k = 2^{k+1} - 1$ vrcholov, a z nich $2^k$ sú listy.

Zjavne pre skoro žiadne $n$ neexistuje úplný binárny strom s $n$ vrcholmi. Budeme sa teda musieť uspokojiť so stromami, ktoré sa na úplné dostatočne podobajú. Takmer úplný binárny strom je taký binárny strom, ktorý má všetky úrovne okrem poslednej plné, a v poslednej sú všetky vrcholy natoľko vľavo, nakoľko sa to pri ich počte dá.

Zjavne pre každé $n$ existuje práve jeden takmer úplný binárny strom s $n$ vrcholmi. Ich konštrukciu môžeme popísať aj takto: Takmer úplný strom s $n>1$ vrcholmi zostrojíme z takmer úplného stromu s $n-1$ vrcholmi tak, že nájdeme najmenšiu úroveň, do ktorej sa dá pridať vrchol, a pridáme ho do nej na najľavejšie možné miesto. Tiež si všimnite, že pre každé $n$ z množiny $\{ 2^k, 2^k + 1, \dots, 2^{k+1} - 1 \}$ má $n$-vrcholový takmer úplný binárny strom hĺbku $k$. Toto isté môžeme povedať aj nasledovne: Takmer úplný binárny strom s $n$ vrcholmi má hĺbku $\lfloor \log_2 n \rfloor$.

Binárna halda

Tak, a sme tu. Po všetkej príprave si konečne ideme vyrobiť konkrétnu vlastnú haldu. A určite už tušíte, ako na to pôjdeme: naša halda (odborne nazývaná binárna halda) bude mať tvar takmer úplného binárneho stromu.

Veľkou výhodou binárnej haldy je, že ju vieme ľahko implementovať bez použitia ukazovateľov (pointrov). Stačí nám jedno dostatočne veľké pole. Haldu doň uložíme "po riadkoch". Teda na začiatku poľa bude uložený koreň, za ním zľava doprava jeho synovia, za nimi zľava doprava ich synovia, a tak ďalej.

index |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 | 
------+----+----+----+----+----+----+----+----+----+----+--
prvok | 47 | 32 | 37 | 23 |  9 | 11 | 18 |  8 | 17 |  5 |

Všimnite si, že $n$-prvková binárna halda nám zaberá presne prvých $n$ pozícii v poli. Ak majú prvky v poli indexy 0 až $n-1$, tak platia nasledovné vlastnosti:

• Otec vrcholu s indexom $x$ má index $\lfloor (x-1)/2\rfloor$.
• Synovia tohoto vrcholu majú indexy $2x+1$ a $2x+2$.

Ku každému vrcholu teda vieme jeho otca aj prípadných synov nájsť v konštantnom čase. Vďaka tomuto nepotrebujeme žiadne pointre, aj bez nich vieme priamo s poľom pracovať tak, ako by sme pracovali s haldou reprezentovanou ako strom.

Výber maxima z binárnej haldy

Vo všeobecnosti môžeme pri výbere z haldy odstrániť ľubovoľný list. Konkrétne pri výbere z binárnej haldy však máme úplne jasnú voľbu: vždy odstránime najpravejší list na najspodnejšej úrovni, teda ten, ktorý je v našom poli uložený na pozícii $n-1$. Odstránením tohto listu totiž opäť vznikne takmer úplný binárny strom.

Pri našej implementácii sa teda udeje nasledovné:

1. Prvok z koreňa (index 0) presunieme do pomocnej premennej.
2. Prvok z indexu $n-1$ presunieme na index 0.
3. Pole o jednu pozíciu zmenšíme. (Presnejšie, nespravíme nič, len sa budeme odteraz tváriť, že je naše pole o jedno kratšie.)
4. Prvok z indexu 0 postupne prebubleme dodola na nejakú pozíciu, na ktorú patrí.

Efektívnosť binárnej haldy

Pri vkladaní prvku nový prvok pridáme do najspodnejšej vrstvy a následne ním prebubleme dohora. Čas potrebný na vloženie prvku je teda v najhoršom prípade priamo úmerný hĺbke haldy.

Keďže v binárnej halde má každý vrchol najviac dvoch synov, vieme pravidlo bublania dodola použiť na ľubovoľný vrchol v konštantnom čase. Celý výber maxima teda tiež vieme spraviť v čase, ktorý je v najhoršom prípade priamo úmerný hĺbke haldy.

No a tu sa ukazuje, prečo bolo dobré zvoliť si práve binárnu haldu. Binárna halda s $n$ prvkami má tvar takmer úplného binárneho stromu, a teda má hĺbku rovnú $\lfloor\log_2 n\rfloor$.

Preto majú obe operácie "vloženie prvku do binárnej haldy" a "výber najväčšieho prvku z nej" časovú zložitosť $O(\log n)$.

Implementácia

Tu je jednoduchý pseudokód funkcií push a pop.

push(co) {
    pole.push_back(co);
    kde = pole.size() - 1;
    while (kde > 0) {
        rodic = (kde-1)/2;
        if (pole[kde] > pole[rodic]) {
            swap( pole[kde], pole[rodic] );
            kde = rodic;
        } else {
            break;
        }
    }
}

pop() {
    n = pole.size();
    odpoved = pole[0];
    swap( pole[0], pole[n-1] );
    pole.pop_back();
    kde = 0;
    while (true) {
        kam = kde;
        if (2*kde+1 < n-1 and pole[2*kde+1] > pole[kam]) kam = 2*kde+1;
        if (2*kde+2 < n-1 and pole[2*kde+2] > pole[kam]) kam = 2*kde+2;
        if (kam != kde) {
            swap( pole[kde], pole[kam] );
            kde = kam;
        } else {
            return odpoved;
        }
    }
}