05.1 Binomiální minimová halda

Last updated Nov 9, 2022

$$ \require{mathtools} \DeclarePairedDelimiter\ceil{\lceil}{\rceil} \DeclarePairedDelimiter\floor{\lfloor}{\rfloor} \newcommand{\dv}[1]{\frac{\mathrm{d}}{\mathrm{d} #1}} \newcommand{\dvv}[2]{\frac{\mathrm{d} #1}{\mathrm{d} #2}} $$

# Binomiální minimová halda

Umí to, co Binární minimová halda, ale i něco navíc
Oproti binární se lépe (rychleji) slučují

Funkce	Složitost	Popis
BHInsert	$O(\log{n}), \Theta^*(1)$	Vloží do BH nový prvek
BHFindMin	$O(1)$	Vrátí minimum monžiny prvků BH
BHExtractMin	$O(\log{n})$	Odstraní z BH minimum množiny jejích prvků
BHMerge	$O(\log{n})$	Sloučí dvě BH do jední
BHBuild	$O(n)$	Postaví z $n$ prvků BH
BHDecreaseKey	$O(\log{n})$	Sníží hodnotu klíče prvku BH
BHIncreaseKey	$O(\log{n})$	Zvýší hodnotu klíče prvku BH
BHDelete	$O(\log{n})$	Smaže prvek BH

BH obsahující $n$ prvků je uspořádaná množina binomiálních stromů $\mathcal{T} = T_{1},\dots,T_{l}$, kde platí:
- Stromy $T_{i}$ jsou v $\mathcal{T}$ uspořádány vzestupně podle svých řádů
- $n = |V(T_{1})|+\cdots+|V(T_{l})|$
- 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íče $k(v)$
- Pro každý strom $T_{i}$ platí haldové uspořádání klíčů

# Paměťová reprezentace

Pro uložení uspořádané množiny stromů $\mathcal{T}$ BH se používá spojový seznam
Vrchol $v$ může vypadat takto:
- Pointer na otce
- Hodnota $k(v)$
- Pointer na levého sourozence
- Pointer na nejpravějšího syna

# Vlastnosti

Binomiální strom $B_{i}$ se vyskytuje v seznamu $\mathcal{T}$ $n$-prvkové BH právě tehdy, když v binárním $b_{k},b_{k-1},\dots,b_{0}$ zápisu čísla $n$ je $b_{i}=1$

# Operace

# Nalezení minima - BHFindMin()

Globální minimum se nachází v jednom z kořenů stromů $T_{i}$
Složitost: Stačí projet seznam $\mathcal{T}$, což bude trvat $O(\log{n})$
Používáme-li tuto funkci často, vyplatí se udržovat pointer na globálně nejmenší kořen, pak je $O(1)$

# Sloučení dvou BH - BHMerge()

Vytvoří jedinou BH, obsahující sjednocení prvků obou vstupních BH
Vyberu menší z kořenů a druhý stromeček zavěsím za něj (jako nejposlednějšího syna)
Podobné binárnímu sčítání pod sebou, přesun do vyššího řádu
Složitost: $O(\log{n})$