Pro přehlednost zkracujeme jako BH.
Podporuje stejné operace jako binární halda.
Navíc je schopna rychle provádět operaci sloučení dvou hald, která má u binární haldy lineární složitost (sloučit dvě binární haldy velikostí $m$ a $n$ má složitost operace HeapBuild haldy velikosti $m + n$).
Binomiální halda patří do rodiny tzv. mergeable heaps. Další dobrou vlastností je vynikající amortizovaná složitost operace vkládání.
Nevýhodou jsou násobně vyšší paměťové nároky než u binární haldy.
BHInsert ($H$, $k$) | $O(\log n)$ / $\Theta^{∗} (1)$ | Vloží do binomální haldy H nový prvek $k$. |
BHFindMin ($H$) | $O(1)$ | Vrátí minimum z binomální haldy H. |
BHExtractMin ($H$) | $O(\log n)$ | Odstraní z BH minimum množiny jejích prvků. |
BHMerge ($A$, $B$) | $O(\log n)$ | Sloučí dvě binomální haldy $A$ a $B$ do jedné. |
BHBuild ($V$) | $O(n)$ | Postaví z $n$ prvků pole $V$ binomální haldu. |
BHDecreaseKey ($H$, $k$) | $O(\log n)$ | Sníží hodnotu klíče $k$ binomální haldy $H$ o 1. |
BHIncreaseKey ($H$, $k$) | $O(\log n)$ | Zvýší hodnotu klíče $k$ binomální haldy $H$ o 1. |
BHDelete ($H$, $k$) | $O(\log n)$ | Smaže prvek $k$ z binomální haldy $H$. |
Tabulka 8.2: Složitosti operací na BH
Binomiální halda (BH) obsahující $n$ prvků je uspořádaná množina binomiálních stromů
kde platí:
Stromy $T_i$ jsou v $\mathcal{T}$ uspořádány vzestupně podle svých řádů.
$n = |V(T_1)| + \dots + |V(T_\ell)|$.
Pro každé nezáporné k se v množině $\mathcal{T}$ vyskytuje nejvýše jeden binomiální strom řádu $k$.
Každý vrchol $v$ v každém stromu obsahuje klíč $k(v)$.
Pro každý strom $T_i$ platí haldové uspořádání klíčů, čili $\forall v \in V (T_i)$ a pro všechny jeho syny $s_j, j = 1, 2, \dots, m$, platí $k(v) \leq k(s_j)$.
Rozmyslete, proč je struktura množiny řádů binomiálních stromů BH určena jednoznačně její velikostí $n$?
Pro uložení uspořádané množiny stromů $\mathcal{T}$ BH se používá spojový seznam.
Seznamy synů jednotlivých vrcholů v binomiálních stromech budeme také udržovat ve spojových seznamech.
Konkrétní implementaci prvku BH si předvedeme později, až budeme znát požadavky na operace, které s BH budeme provádět.
Klíč prvku v budeme v pseudokódu značit $k(v)$.
Binomiální strom $B_i$ se vyskytuje v seznamu $\mathcal{T}$ $n$-prvkové BH právě tehdy, když ve dvojkovém zápisu $b_{k}b_{k−1}\dots b_0$ čísla $n$ je $b_i = 1$
Protože v BH nelze použít dva binomiální stromy stejného řádu a každý binomiální strom $B_i$ přispěje do $n$-prvkové BH právě svými $|V (B_i)| = 2^i$ vrcholy, je poskládání $n$ prvkové BH z binomiálních stromů ekvivalentní zápisu čísla $n$ ve standardní dvojkové soustavě.
$\square$
$n$-prvková BH má až $O(\log n)$ binomiálních stromů.
BHFindMin ($H$))
Minimum celé BH se musí nacházet v jednom z kořenů stromů $T_i$.
Stačí projít seznam $\mathcal{T}$, což bude trvat čas $O(\log n)$.
Používáme-li tuto funkci často, vyplatí se udržovat ukazatel na
tento globálně nejmenší kořen. Operaci BHFindMin lze pak
provést v konstantním čase.
BHMerge
Binomiální haldy jsou nejjednodušším řešením tzv. mergeable heaps, které dokážou velmi efektivně provést operaci sloučení a ostatní operace mají na operaci sloučení postavené.
Operace BHMerge ze dvou BH vytvoří jedinou, obsahující
sjednocení prvků obou vstupních BH.
Nejprve popíšeme operaci BHMergeTree, která slije dohromady
dva binomiální stromy stejného řádu $B_i$ a vytvoří strom $B_{i+1}$ (na to lze nahlížet i jako na sloučení dvou BH tvořených jediným
binomiálním stromem stejného řádu)
Algoritmus 8.3: BHMergeTree
Algoritmus BHMergeTree ($T_1, T_2$), kde řád($T_1$) = řád($T_2$), vytvoří
korektní binomiální strom s řádem řád($T_1$) + 1.
BH lze implementovat tak, že BHMergeTree ($T_1, T_2$) má časovou složitost $O(1)$.
Idea algoritmu:
Mějme BH $A$ a $B$, kde počet prvků $A$ je $a$ a v binárním zápise $a = a_ka_{k−1}\dots a_0$ a počet prvků $B$ je $b = b_{\ell}b_{\ell−1} \dots b_0$.
Výsledná halda $C$ bude mít $c = a + b$ prvků, $c = c_mc_{m−1} \cdot c_0$.
Řády binomiálních stromů ve všech tří haldách jsou jednoznačně určeny binárním zápisem jejich počtu prvků.
Připomeňme „školní“ algoritmus na sčítání binárních čísel a a b pod sebou: jdeme od nejnižších řádů binárního zápisu k nejvyšším a
výsledný bit $c_i = (a_i + b_i + carry_i) \mod{2}$ 1
následně $carry_{i+1} := (a_i + b_i + carry_i) \text{ div} 2$.
Algoritmus na vytvoření BH $C$ nyní zrcadlí předchozí algoritmus sčítání binárních čísel.
Bity $a_i\text{, }b_i\text{, }carry_i$ budou nyní binomiální stromy $A_i , B_i , carry_i$ řádu $i$ nebo prázdné.
Místo sčítání dvou jedničkových bitů voláme BHMergeTree na
dva binomiální stromy stejného řádu, což vytvoří strom vyššího
řádu a tedy přenos $carry$ do dalšího řádu.
Jsou-li všechny tři stromy $A_i\text{, }B_i\text{, }carry_i$ neprázdné, sloučíme $A_i$ a $B_i$ a výsledek se stane přenosem do vyššího řádu $carry_{i+1}$ a do $C_i$ přiřadíme $carry_i$.
Protože udržujeme seznamy binomiálních stromů BH uspořádané dle jejich řádů, lze algoritmus realizovat průchodem dvou ukazatelů po těchto seznamech a přeskakováním řádů stromů nepřítomných v BH.
Algoritmus 8.4: BHMerge
Algoritmus BHMerge je korektní a jeho časová složitost je $O(\log n)$.
V každé iteraci se zpracují všechny stromy řádu $akt\_rad$. Následně se $akt\_rad$ zvýší o jedna. Všechny operace uvnitř cyklu trvají čas $O(1)$. Nejvyšší řád je $O(\log n)$, celkový čas je tedy $O(\log n)$.
$\square$
BHInsert
Algoritmus 8.5: BHInsert
Operace BHInsert má v nejhorším případě složitost $O(\log n)$.
Pro na počátku prázdnou BH trvá posloupnost $n$ volání operace
BHInsert čas $O(n)$. BHInsert má tedy amortizovanou časovou
složitost $O^*(1)$.
Víme, že binomiální stromy tvořící $n$-prvkovou BH přesně odpovídají jedničkovým bitům v dvojkovém zápisu čísla $n$.
Operace BHInsert je sloučení s jednoprvkovou BH a to odpovídá operaci Inc binární sčítačky.
Provedení operace BHMergeTree s $O(1)$ složitostí během BHInsert odpovídá bitové inverzi v operaci Inc
Dle analýzy binární sčítačky má tedy operace BHInsert amortizovanou složitost $O^∗(1)$
$\square$
BHBuild)
Voláním BHInsert $n$ krát po sobě vytvoříme BH o velikosti $n$.
Podle předchozí analýzy bude trvat vytvoření $n$-prvkové BH čas $O(n)$.
BHExtractMin
Algoritmus 8.6: BHExtractMin
Potřebujeme v čase $O(\log n)$ vytvořit BH ze synů (podstromů) stromu $T$.
Toho potřebujeme dosáhnout při zachování $O(1)$ času pro BHMergeTree
Časová složitost operace BHExtractMin je $O(\log n)$.
Kroky (1) a (2) trvají čas $O(1)$, stačí si udržovat minimový
ukazatel na strom a vypojit ho ze seznamu.
Kroky (3) a (4) trvají $O(\log n)$, protože kořen binomiálního
stromu má nejvýše $O(\log n)$ synů.
Sloučení hald trvá $O(\log n)$, včetně rekonstrukce minimového ukazatele.
$\square$
Prvek v BH bude v počítači reprezentován pomocí následující struktury:
| ukazatel na otce |
| hodnota $k(v)$ |
| ukazatel na levého sourozence |
| ukazatel na nejpravějšího syna |
BHMergeTree i vytvoření BH ze seznamu synů kořene lze v čase $O(\log n)$, kde $n$ je počet prvků ve výsledné BH.
Jak v minimové BH udělat operace:
BHDecreaseKey v čase $O(\log n)$?
BHDelete v čase $O(\log n)$?
BHIncreaseKey v čase $O(\log n)$?
(Všechny operace dostanou ukazatel na prvek, se kterým se pracuje.)
Binomiální strom řádu $k$ (značíme $B_k$) je uspořádaný (t.j. záleží na pořadí synů) zakořeněný strom, pro který platí:
$B_0$ je tvořen pouze kořenem.
Pro $k \geq 1$ získáme $B_k$ ze stromů $B_0, B_1, . . . , B_{k−1}$ tak, že přidáme nový kořen a kořeny těchto stromů uděláme (takto popořadě) syny nového kořene.