{{TIN066 Skripta}}
{{TODO|aplikace}}
== 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> vyrobíme tak, že vezmeme dva <math>H_{i}</math> a jeden z nich přidáme jako dalšího syna kořene toho druhého. (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 je opět konkatenace obou hald (množin stromů), stejně funguje dokonce i DELETEMIN s pomocnými procedurami OPRAV a SPOJ. To skutečně zajímavé přichází teprve teď - DECREASE a INCREASE. Vzpomínáte na leftist haldy? Tam jsme udělali to, že jsme jednoduše celý podstrom utrhli, zbytek haldy opravili a vše zmergovali. To samé uděláme teď! Jen si musíme zase říci, co znamená opravení - OPRAV2 postupně vytrhává rodiče odtrhnutého prvku, dokud jsou označení; když se zastaví před kořenem, neoznačený vrchol označí. Takže ze začátku při odtrhávání jen značkujeme rodiče, až když z nějakého rodiče odtrhneme víc než jednoho syna, vytrhneme i rodiče; při tom jej přirozeně odznačíme, kořen nemůže být označený.
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.
