{{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 ==
Binomiální halda je divný vynález. Abychom pochopili, v čem ji vlastně ukládáme, definujme si ''rekurentní binomiální stromy'':
* <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>.
Takže <math>H_{i}</math> má v kořeni i synů, celkem <math>2^i</math> vrcholů a hloubku i. Podívejte se třeba na obrázek ve skriptech.
Jak vypadá binomiální halda? Vezmeme hromádku binomiálních stromů (každý jinak velký, ale ne nutně jeden od každé velikosti) a do nich nasypeme naše prvky. (Pro každý počet prvků existuje správná hromádka binomiálních stromů - vezměme si binární zápis počtu, pak jednička na i-tém místě znamená, že zahrneme <math>H_i</math>.)
No dobře, ale jak s takovou obludou zacházet? Operace opět založíme na MERGE a DECREASE (OPRAV) a budeme je jednoduše provádět "po složkách". MERGE je vlastně sčítání dvou binárních čísel: pokud konkrétní H-množina existuje jen v jedné z hald, přeneseme ji do výsledné, pokud sčítáme dvě H-množiny nebo jednu a přenos T, ve výsledku bude tahle H-množina prázdná a operací SPOJ (viz níže) vyrobíme přenos T, pokud se nám sejdou H-množiny z obou i přenos, nová H-množina bude přenost T a SPOJem vyrobíme z mergovaných H-množin nový přenos. A SPOJ? Jednoduše z definice binomiálních stromů - vybereme kořen z obou kandidátů podle haldové podmínky a druhý strom připojíme k synům.
''(Asi to je takhle trochu chaotické; pro formální zápis se mrkněte jinam a pak ho sem třeba doplňte, ale je to vážně prostě jako sčítání čísel v binárním zápisu.)''
Mezi jednotlivými složkami uspořádání nemáme, takže MIN musí projít kořeny všech (tj. O(log N)). DELETEMIN smaže kořen haldičky, haldička se rozpadne na menší haldičky - ty (z definice binomiálního stromu) tvoří novou binomiální haldu, kterou přimergujeme k té původní. DECREASE/INCREASE děláme pomocí UP/DOWN jako u regulárních hald. DELETE uděláme třeba pomocí DECREASE o nekonečno a DELETEMIN.
Co složitost? Korespondence s binárními čísly se hodí, MERGE má složitost jako sčítání binárních čísel O(logN); INSERT se implementuje jako MERGE s jednoprvkovou haldou, takže taky O(log N); DELETEMIN = MIN & roztrhat haldičku & MERGE, každé je O(log N), dohromady tedy opět O(log N). MAKEHEAP (posloupnost INSERTů) zase využívá faktu, že přičítání jedniček k binárnímu číslu má amortizovanou složitost O(N). Každá haldička má výšku O(log N) a počet synů kořene je taky O(log N) (viz třeba halda o 256 prvcích (resp. lib. <math>2^i</math>), která se skládá jen z jedné haldičky), proto je DECREASE O(log N) a INCREASE <math>O(log^2N)</math>.
Nic moc - proč jsou tedy binomiální haldy zajímavé? Jednak jdou zobecnit na Fibonacciho haldy, druhak naimplementovat líně, jak si teď ukážeme.
=== 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.
