TIN066 Binomické a Fibonacciho haldy

Z ωικι.matfyz.cz
Přejít na: navigace, hledání
Tato část je neúplná a potřebuje rozšířit. aplikace

Vhodné zdroje:

Binomiální haldy

Definice: binomiální strom $ H_i $ (strom řádu i):

  • $ H_0 $ je jediný uzel, samotinký
  • $ H_{i+1} $ je kořen, jehož potomci jsou binomiální stromy $ H_{i}, H_{i-1}, ... H_{1}, H_{0} $.

Tvrzení : pro strom $ H_i $ platí:

  • má $ 2^i $ vrcholů
  • kořen má $ i $ synů
  • výška stromu je $ i $

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 $ O_i $ stromů se stejným rankem a vyrobí haldu s max. jedním stromem od každého ranku

  • H = {}
  • pro každé $ O_i $
    • while ($ O_i $ má aspoň 2 stromy A, B) vyndej je, přidej SPOJ(A,B) do $ O_{i+1} $
    • pokud má $ O_i $ jeden strom A, přidej A do H

MIN: Projdu všechny kořeny, vyberu nejmenší hodnotu. Nakonec "sgrupuju" stromy do skupin $ O_{i} $ 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 $ O_{i} $ 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(|H|) a DELETEMIN O(|H|+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ť $ \varphi(n) $ 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 $ O(\varphi(n)) $.

Klíčová otázka - kolik je $ \varphi(n) $? 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ší $ \log^{-1}(3/2)\cdot\log(\sqrt{5}N+1) $ - chachá! Proč?

Důkaz počtu synů

Výkon Fibonacciho haldy úzce závisí na podobě stromů. Níže ukážeme, že např. nemůže vzniknout strom, kde na uzel je napojeno 10 nebo víc "listů".

Každý uzel může dostávat nové syny "vpravo". Uzel však může přijít nejvýše o jednoho syna. Při mazání prvního syna se vrchol označkuje. Při příštím mazání již nelze mazat, halda se musí přestavět.

Věta: Má-li vrchol v právě d synů, podstrom tímto vrcholem určený má alespoň $ F_{d+2} $ vrcholů ( d-plus-druhé fibonacciho číslo).

  • Když má vrchol X nula synů, podstrom má velikost $ F_2=1 $, pro 1 syna má podstrom velikost $ F_3=2 $.
  • Když má vrchol X syny $ y_1, y_2, ... y_d $, ukažme, že každý i-tý syn má aspoň i-2 vlastních synů. Když se Yi připojoval pod X, ten již měl i-1 synů. Při spojení musel mít Yi také i-1 synů. Během dalších úprav mohl přijít max. o 1 syna, tedy stále má aspoň i-2 vlastních synů.
  • Označme size(X) velikost podstromu s kořenem X, aplikujme indukci. Potomek Yi s k syny má dle indukčního předpokladu $ size(y_i) \geq F_{k+2} \geq F_{(i-2)+2} = F_i $. Nyní odhadneme $ size(X) = 1 + \sum size(y_i) \geq 1 + \sum F_i = F_{d+2} $.
Citováno z „http://wiki.matfyz.cz/index.php?title=TIN066_Binomické_a_Fibonacciho_haldy&oldid=36152“