{{TIN066 Skripta}}
{{TODO|aplikace}}
Vhodné zdroje:
* [http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/xl-fiboheap.pdf Skripta Jeffa Ericksona]
* [http://www.cs.princeton.edu/~wayne/teaching/fibonacci-heap.pdf Slajdy z Princetonu s obrázky ke všem operacím]
* [http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-854j-advanced-algorithms-fall-2005/lecture-notes/fibheaps.pdf Jeste jeden material k Fibohaldam, z MIT]
== Binomiální haldy ==
Definice: '''binomiální strom''' <math>H_i</math> (strom řádu i):
* <math>H_0</math> je jediný uzel, samotinký
* <math>H_{i+1}</math> je kořen, jehož potomci jsou binomiální stromy <math>H_{i}, H_{i-1}, ... H_{1}, H_{0}</math>.
'''Tvrzení''' : pro strom <math>H_i</math> platí:
* má <math>2^i</math> vrcholů
* kořen má <math>i</math> synů
* výška stromu je <math>i</math>
Definice: '''binomiální halda''' pro množinu prvků S je množina binomiálních stromů takových, že:
* vrcholy stromů jsou ohodnoceny prvky z S, je zachována haldová podmínka (syn není menší než otec)
* nejsou zde 2 stromy stejného řádu
Řády stromů v haldě lze snadno vidět z binárního zápisu velikosti S. Vidíme také, že existuje bin. halda pro libovolně velké S.
=== Algoritmy ===
'''spoj T1, T2''' - spojí dva stromy řádu ''i'' do jednoho stromu řádu ''i+1''
* pokud (kořen T2 < kořen T1) prohoď T1, T2
* přidej T2 jako syna k T1
'''MERGE H1, H2''' - spojí dvě haldy. Slévání odpovídá sčítání čísel v binárním zápisu. Může nastávat "posun do vyššího řádu".
* H = {}, posun = null;
* pro i = 0 ..
** stromy = { strom řádu ''i'' z H1, strom řádu ''i'' z H2, posun } // vyberu všechny stromy daného řádu
** pokud (3 stromy) přidej strom[0] do H, posun = spoj(strom[1], strom[2]);
** pokud (2 stromy) posun = spoj(strom[1], strom[2]);
** pokud (1 strom ) přidej strom[0] do H; posun = null;
** pokud (0 stromů) nic ...
'''INSERT x''' : MERGE(T, {x});
'''MIN x''' : projdu kořeny všech stromů, vyberu nejmenší.
'''DECREASE v, z''' : zmenším hodnotu ''v'' o ''z''. Probublám nahoru, dokud je menší než otec.
'''DELETE MIN''' : najdu strom s minimem v kořenu, vyndám ho z haldy, jeho oba syny přimergeuji k haldě.
'''Věta''' : Operace MERGE, INSERT, DECREASE, MIN, DELETE MIN běží v O(log n).
=== Líné binomiální haldy ===
Potřebujeme demo na amortizovanou složitost ;-) - udělejme to, že "vyvažovat" haldy budeme jen, když z nich budeme potřebovat něco vytáhnout. To znamená, že zahodíme podmínku, aby jednotlivé stromy haldy byly různého řádu, a operace MERGE bude jednoduše konkatenace stromů z obou hald. Naopak při vykonávání operací MIN a DELETEMIN provedeme pomocnou proceduru VYVAZ, která nám haldu srovná - pro každý řád stromu testuje, zda jich máme víc než jeden, a vždy vybírá dvojice takových a provádí na nich SPOJ, dokud nám od daného řádu zbývá nejvýše jeden strom; pak pokračuje s vyšším řádem.
MERGE, INSERT, apod. jsou tak O(1), zato MIN a DELETEMIN až O(N). Pointa je však ta, že jejich amortizovaná složitost je jen O(logN).
Cože? Jakto? Inu, amortizovanou složitost počítáme jako ''doba_běhu + ohodnocení_po - ohodocení_před''; ohodnocení nějak vyjadřuje nepohodlnost aktuální struktury, klíčové je, že v našem případě jako ohodnocení zvolíme počet stromů v haldě. Na začátku jich může být až N, běh může taky trvat až N, ale po doběhnutí už bude stromů jen logN, tak se nám to pěkně vyruší.
== Fibonacciho haldy ==
Náš cíl je mít strukturu, která bude mít amortizovanou složitost DELETEMIN stále O(logN), ale INCREASE/DECREASE budou trvat amortizovaně jen O(1). Fibonacciho haldy jsou vpodstatě stejné jako líné binomiální haldy, ovšem s dvěma rozdíly - stromy nebudeme třídit podle jejich isomorfismu s H-čkovými binomiálními stromy, ale podle jejich ''ranku'', totiž počtu synů kořene - něco dost podobného, ale neklademe přísné požadavky na vnitřní strukturu. Druhak si můžeme některé vrcholy mimo kořen označkovat - vrchol je označený, když mu byl někdy odříznut syn (to se nám bude hodit při INCREASE/DECREASE). Přesně popsat vnitřní strukturu jednotlivých stromů je těžké, tak prostě řekneme, že to jsou takové, které umíme vygenerovat jednotlivými algoritmy.
'''MERGE A, B''': Konkatenace obou hald. O(1).
'''INSERT x''': Konkatenace haldy s jednoprvkovou haldou {x}. O(1).
'''SPOJ T1, T2''': funkce spojí dva stromy ranku ''k'' a vytvoří jeden strom ranku ''k+1''
* pokud kořen(T1) > kořen(T2) prohoď T1, T2
* připoj T2 jako dalšího potomka ke kořenu T1
'''VYVAZ1 Oi''': funkce dostane skupiny <math>O_i</math> stromů se stejným rankem a vyrobí haldu s max. jedním stromem od každého ranku
* H = {}
* pro každé <math>O_i</math>
** while (<math>O_i</math> má aspoň 2 stromy A, B) vyndej je, přidej SPOJ(A,B) do <math>O_{i+1}</math>
** pokud má <math>O_i</math> jeden strom A, přidej A do H
'''MIN''': Projdu všechny kořeny, vyberu nejmenší hodnotu. Nakonec "sgrupuju" stromy do skupin <math>O_{i}</math> dle ranku a zavolám VYVAZ1.
'''DELETE MIN''': Projdu všechny kořeny, najdu strom s nejmenší hodnotou kořene, vyndám ho. Jeho potomky přimerguju ke zbytku haldy. Nakonec "sgrupuju" stromy do skupin <math>O_{i}</math> dle ranku a zavolám VYVAZ1.
Při mazání vrcholů by mohly stromy získat nepěknou strukturu (např. počet uzlů = výška stromu), kvůli tomu bylo vymyšleno označování vrcholů a s ním spojené operace.
'''VYVAZ2 T, v''': tato funkce označí předka v a pokud už byl označený, odtrhne jeho podstrom zkusí označení "výše" směrem ke kořenu.
* u = otec v
* dokud u označen
** zruš označení u
** odrthni podstrom s kořenem u a vlož ho do haldy; u = otec u
* pokud u není kořen, označ u
'''DECREASE v, z''': sníží hodnotu v o z
* pokud v je kořen, sniž hodnotu, konec
* VYVAZ2 (T, v), zruš případné označení v, sniž hodnotu v
* odtrhni podstrom určený v a přidej ho do haldy
'''INCREASE v, z''': zvýší hodnotu v o z
* pokud v je list, zvyš hodnotu, konec
* VYVAZ2 (T, v), zruš případné označení v, zvyš hodnotu v
* pro všechny u syny v: zruš případné označení u, přidej podstrom s kořenem u do haldy;
* přidej jednoprvkový strom {v} do haldy
'''DELETE v''': lze provést jako DECREASE(v, -nekonečno) a následné DELETE MIN.
Abychom si to shrnuli:
* MERGE O(1), INSERT O(1), DECREASE O(1+c), INCREASE O(1+c+d) a DELETE O(1+c+d) nám generují spoustu stromů
* MIN O(N) a DELETEMIN O(N+d) nám je zase shrabují dohromady.
(c=počet odznačených vrcholů, d=počet synů vrcholu).
Teď to potřebujeme nějak zamortizovat. Jako ohodnocovací funkci struktury si vezměme počet stromů + 2 * počet označených vrcholů. Nechť <math>\varphi(n)</math> je maximální počet synů nějakého vrcholu ve Fibonacciho haldě, která reprezentuje n-prvkovou množinu. Pak MERGE, INSERT, DECREASE je O(1), MIN, DELETEMIN, INCREASE a DELETE je <math>O(\varphi(n))</math>.
Klíčová otázka - kolik je <math>\varphi(n)</math>? Ukazuje se, že O(logN). Zatímco u binomiálních hald byl počet možných tříd stromů logN, tady bude přesná hodnota podstatně brutálnější <math>\log^{-1}(3/2)\cdot\log(\sqrt{5}N+1)</math> - chachá! Proč?
=== Důkaz počtu synů ===
Tvrdíme: Má-li vrchol v právě i synů, podstrom tímto vrcholem určený má alespoň <math>F_{i+2}</math> vrcholů:
* Nejdříve, že pro vrchol ''v'' má i-tý nejstarší syn ''u'' sám alespoň i-2 synů (když se u stával synem v operací SPOJ, v měl i-1 synů (aby u byl i-tý nejstarší), dle předpokladu SPOJ oba měly stejně synů, a od té doby od u mohl upadnout max. jeden syn).
* Pak indukcí podle nejdelší cesty do listu.
No dobře, teď tvrzení využijme, abychom podle velikosti stromu odhadli počet synů. Najděme nejmenší Fibonacciho číslo <math>F_i</math> větší než n - počet vrcholů ve stromě. Z tvrzení teď víme, že <math>\varphi(n) < i-2</math>.
Teď jen jak z n vyrobit i.
Vezměme prostě explicitní vzorec na výrobu Fibonacciho čísel (ten můžeme dokázat indukcí):
<math>F_i = {1 \over \sqrt{5}}\left({1 + \sqrt{5} \over 2}\right)^i - {1 \over\sqrt{5}}\left({1 - \sqrt{5}\over2}\right)^i</math>
Zbytek už jsou takové algebraické hrátky. Pomocí magických odhadů <math>0>{1-\sqrt{5}\over2}>-3/4</math> a <math>\sqrt{5}>2</math> vyrobíme něco jako:
<math>n \le {1\over\sqrt{5}}\left({1+\sqrt{5}\over2}\right)^i-3/8</math>
Směr je jasný, zlogaritmujeme a vypadne nám kýžená horní mez.
