Definice:  Stromová datová struktura je reprezentace stromu v počítači. V každém vrcholu $v$ si pamatujeme hodnotu $x(v)$, které se říká klíč (key).

Halda je stromová datová struktura splňující vlastnost haldy. Zakořeněný strom má vlastnost haldy právě tehdy, když pro každý uzel $v$ a pro každého jeho syna $w$ platí $x(v)\leq x(w)$. Díky této vlastnosti bude kořen stromu obsahovat nejmenší klíč z celé haldy.

Binární halda je úplný binární strom s vlastností haldy. Strom je binární, pokud má každý vrchol nejvýše dva potomky. Binární strom je úplný, pokud jsou všechny jeho hladiny kromě poslední úplně zaplněny a v poslední hladině leží listy co nejvíce vlevo. Úplnost binárního stromu zaručuje hezký vyvážený tvar stromu a to nám garantuje výšku stromu nejvýše $\lceil\log n\rceil$. Příklad binární haldy je na obrázku vpravo.1

Operace: s haldou běžně provádíme následující operace:

  • MIN — vrátí nejmenší klíč v haldě
  • DELMIN — vymaže uzel s nejmenším klíčem
  • INSERT($h$) — přidá nový uzel s hodnotou $h$
  • DELETE($v$) — smaže uzel $v$
  • DECREASEKEY($v$, $okolik$) — uzlu $v$ zmenší hodnotu klíče o okolik
  • INCREASEKEY($v$, $okolik$) — uzlu $v$ zvětší hodnotu klíče o okolik
  • MAKE — dostane pole $n$ prvků a vytvoří z nich haldu.

Binární haldu si můžeme snadno reprezentovat v poli $\ARRAY{x}{\cdot}$. Využijeme při tom úplnosti binárního stromu. Uzly stromu očíslujeme po hladinách počínaje od jedničky. Těmito čísly budeme uzly označovat. Uzel $i$ uložíme do $\ARRAY{x}{i}$. Levý syn uzlu $k$ bude uložen na pozici $2k$ a pravý syn uzlu $k$ na pozici $2k+1$. Naopak otec vrcholu $k$ se bude nacházet na pozici $\lfloor k/2 \rfloor$. Na následujícím obrázku jsme takto do pole poskládali binární strom z předchozího obrázku.

Aby se nám s haldou lépe pracovalo, zavedeme si dvě pomocné funkce BUBBLEUP($v$) a BUBBLEDOWN($v$). Bublání funguje stejně jako v třídění pomocí bublinkového algoritmu, akorát místo průchodu pole probubláváme podél cesty ve stromě vedoucí z uzlu $v$ do kořene nebo do listu. BUBBLEUP zajistí probublání lehkých prvků směrem nahoru ke kořeni. BUBBLEDOWN naopak zajistí propad těžkých prvků dolů směrem k listům. Nebudeme probublávat podél celé cesty, ale jen dokud v aktuálním vrcholu není splněna vlastnost haldy. Pomocí swap($i$, $j$) značíme prohození dvou prvků na pozicích $i$ a $j$ v poli $\ARRAY{x}{\cdot}$.

BUBBLEUP(k):
	while $k>1$ and $\ARRAY{x}{\lfloor k/2\rfloor} > \ARRAY{x}{k}$ do
		 swap($k$, $\lfloor k/2\rfloor)$
		 $k := \lfloor k/2\rfloor$
BUBBLEDOWN(k):
	while $k\leq \lfloor n/2 \rfloor$ do
		 $min := 2k$ {$min$ bude pozice syna s menším klíčem }
		 if $2k+1\leq n$ and $\ARRAY{x}{2k} > \ARRAY{x}{2k+1}$ then
			 $min:=2k+1$
		 if $\ARRAY{x}{min} < \ARRAY{x}{k}$ then
			  swap($k$, $min$) 
		 else
			  break 
		 $k:=min$

Časová složitost obou probublávacích funkcí je nejvýše tolik, kolik je výška úplného binárního stromu a to je $\OO(\log n)$. Pomocí pomocných funkcí už snadno naimplementuje ostatní operace haldy.

MIN:
	 return $\ARRAY{x}{1}$
DELMIN:
	 $\ARRAY{x}{1} := \ARRAY{x}{n}$ 
	 $n:=n-1$ 
	 BUBBLEDOWN($1$)
INSERT($h$):
	 $n:=n+1$ 
	 $\ARRAY{x}{n} := h$ 
	 BUBBLEUP($n$)
DELETE($k$):
	 $val:= \ARRAY{x}{k}$ 
	 $\ARRAY{x}{k} := \ARRAY{x}{n}$ 
	 $n:=n-1$ 
	 if $val \leq \ARRAY{x}{k} $ then  
		 BUBBLEDOWN($k$) 
	 else 
		 BUBBLEUP($k$)
DECREASEKEY($k$,$okolik$):
	 $\ARRAY{x}{k} := \ARRAY{x}{k} -  okolik$ 
	 BUBBLEUP($k$)
INCREASEKEY($k$,$okolik$):
	 $\ARRAY{x}{k} := \ARRAY{x}{k} +  okolik$ 
	 BUBBLEDOWN($k$)

Časová složitost MIN je konstantní. Časová složitost ostatních výše uvedených operací je stejná jako časová složitost BUBBLEUP nebo BUBBLEDOWN a to je $\OO(\log n)$.

Podívejme se na to, jak z $n$ prvků na vstupu postavit haldu. Jednoduše bychom mohli začít s prázdnou haldou a $n$-krát zavolat operaci INSERT. To by mělo časovou složitost $\OO(n\log n)$. My si ale ukážeme, jak postavit haldu z $n$ prvků v poli v lineárním čase. Prvky necháme v poli $\ARRAY{x}{\cdot}$ tak, jak jsme je dostali na vstupu a nad polem si představíme binární strom. Naším cílem je přeuspořádat prvky tak, aby splňovaly vlastnost haldy. Dosáhneme toho postupným voláním BUBBLEDOWN.

MAKE:
	for $i:=\lfloor n/2 \rfloor$ downto $1$ do
		 BUBBLEDOWN(i)

Proč po skončení MAKE splňuje každý vrchol vlastnost haldy? Platí invariant, že v každém kroku algoritmu splňují všechny vrcholy $j$, pro $i \leq j \leq n$, vlastnost haldy. V následujícím kroku necháme klíč ve vrcholu $i-1$ probublat dolů, takže také vrchol $i-1$ bude splňovat vlastnost haldy. U vrcholů $j$, pro $i \leq j \leq n$, se tím vlastnost haldy neporuší.

Nyní dokážeme, že postavení haldy pomocí MAKE bude trvat jen $\OO(n)$. Nechť $h=\lceil\log n\rceil$ je výška úplného binárního stromu na $n$ vrcholech. Operace BUBBLEDOWN zavolaná na uzel v $k$-té hladině od zdola bude trvat čas přímo úměrný $k$. Z vlastností binárního stromu víme, že v následující hladině stromu je dvojnásobek prvků. Proto je v $k$-té hladině od zdola $2^{h-k}$ prvků. Označíme-li časovou složitost operace MAKE pomocí $X$, dostaneme $$X=\sum_{k=1}^h 2^{h-k}\cdot k.$$ Sumu lze spočítat fintou tak, že ji vynásobíme dvěma a odečteme od ní tu samou sumu. Koeficienty před stejnou mocninou dvojky se krásně odečtou a zbude nám jednoduchá suma. Konkrétně pro člen $2^{h-k}$ máme $2\cdot k 2^{h-k} – (k-1)2^{h-k+1} = 2^{h-k}$. Celkem dostaneme $$X = 2X-X = 2^h + \sum_{k=1}^{h-1} 2^{h-k} – 2^0 h = \sum_{j=0}^h 2^j – 1 – h = 2n – \lceil\log n\rceil = \OO(n).$$

Poznámka (k implementaci):  Operace BUBBLEUP($k$) a BUBBLEDOWN($k$) můžeme implementovat lépe. Místo prohazování dvou sousedních prvků na procházené cestě $P$ ve stromě si zapamatujeme počáteční hodnotu $val:=\ARRAY{x}{k}$, na cestě $P$ budeme procházené prvky posouvat o jedna a hodnotu $val$ uložíme až na konečnou pozici.
Poznámka: Existují i jiné implementace haldy a haldových operací.

  • (pole) Nejjednodušší realizace haldových operací je v poli. Prvky necháme v poli tak, jak jsme je dostali. Nalezení minima realizujeme průchodem celého pole v čase $\OO(n)$. Všechny ostatní operace realizujeme přímým přístupem do pole v čase $\OO(1)$. Přidávané prvky vložíme na konec pole a zvětšíme velikost pole o $1$. Mazání prvku provedeme tak, že mazaný prvek nahradíme posledním prvkem a pole o jedna zkrátíme.
  • ($d$-regulární halda) Zobecněním binární haldy je $d$-regulární halda. Od binární se liší pouze tím, že každý vrchol má nejvýše $d$ synů. Podmínka na úplnost stromu (zaplněnost hladin) zůstává. Více se o $d$-regulární haldě dozvíte ve cvičeních.
  • (Fibonacciho halda) Fibonacciho halda pochází od Fredmanna a Tarjana. Fibonacciho halda pro změnu slevuje z úplnosti stromu, ale stále vyžaduje rozumnou zaplněnost hladin (“košatost” binárních stromů). Fibonacciho halda je množina stromů splňujících vlastnost haldy. Stromy v haldě jsou různého stupně $0$, $1$, $2$,\dots, $k$. Stupeň stromu zhruba odpovídá stupni grafu v kořeni. S rostoucí vzdáleností od kořene klesá i maximální povolený stupeň ve vrcholech stromu. Dá se ukázat, že strom stupně $d$ obsahuje alespoň $\Phi^d$ vrcholů, kde $\Phi=(1+\sqrt{5})/2$.Nejhorší případ stromu stupně $d$, tj. nejmenší a tedy i nejméně košatý strom, jaký je povolen, se konstruuje složením nejmenších stromů stupně $d-1$ a $d-2$. Počet vrcholů v nejmenším stromu stupně $d$ je $F_{d}=F_{d-1}+F_{d-2}$. Formulka je stejná jako při výpočtu Fibonacciho čísel, proto se této haldě říká Fibonacciho halda.Fibonacciho halda realizuje operace MIN, INSERT, DECREASEKEY, INCREASEKEY v amortizovaném čase $\OO(1)$ a operace DELMIN a DELETE v amortizovaném čase $\OO(\log n)$. Implementace této haldy je podstatně složitější a konstanty před časovými složitostmi jednotlivých operací jsou poměrně vysoké. Na druhou stranu použitím Fibonacciho haldy můžeme dosáhnout podstatně lepších asymptotických časových složitostí.

Následující tabulka shrnuje časové složitosti jednotlivých operací při různých reprezentacích.

DELMIN DELETE INSERT
DECREASEKEY
INCREASEKEY
pole $\OO(n)$ $\OO(1)$ $\OO(1)$ $\OO(1)$
binární halda $\OO(\log n)$ $\OO(\log n)$ $\OO(\log n)$ $\OO(\log n)$
$d$-regulární halda $\OO(\frac{d\log n}{\log d})$ $\OO(\frac{d\log n}{\log d})$ $\OO(\frac{\log n}{\log d})$ $\OO(\frac{d\log n}{\log d})$
Fibonacciho halda $\OO(\log n)$ $\OO(\log n)$ $\OO(1)$ $\OO(1)$

Pozor, u Fibonacciho haldy je všude uvedena amortizovaná časová složitost.

Všimněme si, jak parametr $d$ u $d$-regulární haldy interpoluje mezi polem a binární haldou (pro $d=2$ dostaneme binární haldu a pro $d=n$ realizaci v poli). Optimální hodnota parametru $d$ se hledá tak, aby celková časová složitost algoritmu, ve kterém haldu používáme, byla co nejmenší.