Dobré a zlé tvary haldy

Zlé tvary haldy

Haldy rôznych degenerovaných tvarov nám príliš nepomôžu. Napr. je nanič halda, ktorá je tvorená jedným koreňom a $n−1$ listami. A takisto je nanič halda-had, v ktorej má každý vrchol najviac jedného syna.

V čom je problém?

Pozrime sa najskôr na prvú spomínanú haldu. Keby sme v našom programe používali haldu, ktorá vyzerá takto, príliš by nám to nepomohlo. Zjavne do takejto haldy vieme ľahko vkladať ďalšie prvky ­— stačí pridať nový list a ak treba, tak hodnotu v ňom vymeniť s hodnotou v koreni. Avšak do problémov sa dostávame v okamihu, keď by sme chceli najmenší prvok z haldy vybrať. Vtedy by sme totiž na to, aby sme zistili, ktorú hodnotu presunúť do koreňa, museli prezrieť úplne všetky prvky v halde. Vieme teda robiť push v konštantnom čase, ale na pop potrebujeme až lineárny čas. (Takáto halda v podstate zodpovedá ukladaniu prvkov v neusporiadanom poli, až na to, že aktuálne maximum máme akoby v samostatnej premennej.)

A o nič lepšie na tom nie je ani druhá spomínaná halda. Vždy, keď vložíme nový prvok, ho pridáme ako nový list do najhlbšej úrovne a následne hodnotou z neho bubleme dohora, až kým sa nezastaví. V najhoršom možnom prípade (ktorý nastane, ak budeme vkladať prvky v poradí od najmenšieho po najväčší) teda každý prvok postupne prebuble hore celou reťazou až do koreňa. Teda druhý vložený prvok bude bublať dohora $1$-krát, tretí $2$-krát, \dots, a ak ich vložíme postupne $n$, tak posledný bude bublať dohora až $(n−1)$-krát. Tu teda operácia push môže trvať až lineárne dlho. A niet divu: ľahko nahliadneme, že takáto halda čítaná zhora dole je vlastne obyčajným usporiadaným poľom.

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ýš $2k$ 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+ \dots +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 log2n \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.

Obrázok 5: Binárna maximová halda obsahujúca 10 prvkov.

Veľkou výhodou binárnej haldy je, že ju vieme ľahko implementovať bez použitia referencií alebo 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 stane 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)$.