{{TIN066 Skripta}}
Mějme uspořádané univerzum, naší strukturou "protékají" prvky, chceme rychle najít další prvek na vytažení, na druhou stranu nepotřebujeme efektivní MEMBER a u DELETE budeme znát přesnou pozici ve struktuře. Máme uspořádávací funkci <math>f\colon S \to \mathbb{R}</math>, tu navíc chceme moci změnit operacemi INCREASE (zvýší hodnotu prvku) a DECREASE (sníží hodnotu). Nakonec máme navíc ještě operace:
* MIN - nalezení prvku s nejmenší hodnotou f
* DELETEMIN - smazání prvku s nejmenší hodnotou f
* MAKEHEAP - máme S a f, vyrobíme haldu
* MERGE - vyrobí konjunkci dvou hald (neověřuje jejich disjunknost)
Pak '''halda''' je strom, který splňuje ''podmínku haldy'': <math>\forall x \in S: f(otec(x)) \le f(x)</math>. (Tato podmínka se nazývá ''usp'', protože zajišťuje správné ''usp''ořádání; takhle napsaná platí pro min-heap, může se definovat i opačně, pak dostaneme max-heap.)
{{TODO|vice formalne}}
== Regulární haldy ==
Regulární halda je d-regulární strom splňující podmínku haldy. A d-regulární strom je takový, kde každý uzel má nejvýše d synů a je "shora a zleva" naplněný (prostě jakobyste ten strom měli v poli a do něj zleva nasypali souvislý blok prvků). Dá se dokázat, že nejvýše jeden ne-list má méně než d synů a hloubka stromu je logaritmická (O(log_d(N*d)), jsou tam nějaké +- 1, přesně to jde odvodit s pomocí vzorce pro součet geometrické posloupnosti).
Nejdříve potřebujeme "primitivní operace" UP a DOWN. UP probublává prvek nahoru, dokud porušuje podmínku haldy (prohodí s otcem), DOWN naopak ponořuje prvek dolů (prohodí s nejmenším synem). INSERT přidá prvek jako poslední prvek a pustí UP, DELETEMIN prohodí kořen s posledním listem, odebere a pustí DOWN. DELETE prohodí prvek s posledním listem, odebere a pustí UP nebo DOWN podle situace. DECREASE upraví a pustí UP, INCREASE upraví a pustí DOWN. Při MAKEHEAP nasypeme prvky do stromu (pole) a od konce bereme postupně prvky a voláme na ně DOWN.
UP je O(log_d N), DOWN je O(d * log_d N) (to proto, že když bublám nahoru, porovnávám jen sebe s otcem, zatímco když bublám dolu, musím najít nejmenšího ze synů), z toho vyplývají ostatní složitosti - složité je jen MAKEHEAP, dá se dokázat, že je jen <math>O(dN)</math>.
Složitost pořádně.
=== Aplikace ===
==== Heapsort ====
Postavím haldu (MAKEHEAP) a pak dělám MIN & DELETEMIN, dokud tam něco je, prvky mi z toho padaj ve vzestupném pořadí. Nejvíc se prý hodí 6-regulární nebo 7-regulární haldy.
==== Dijkstra ====
Aka hledání nejkratších cest z jednoho vrcholu ''z'' do všech ostatních vrcholů (v neorientovaném grafu s ohodnocenými hranami).
V haldě mám dosud nepořešené vrcholy ''v'', které jsou sousedy vrcholů, které už pořešené mám (na začátku tedy jen sousedy ''z''), klíčem je jejich vzdálenost od vrcholu ''z'' (''d(z, v)'', na začátku tedy ohodnocení hrany ''e(z,v)''). Vždycky vezmu MIN (''u'') (to je vrchol, jehož vzdálenost od ''z'' už nebude menší, a tedy to můžu poslat na výstup), udělám DELETEMIN, a do haldy přidám jeho sousedy (''v''), pokud tam ještě nejsou (a samozřejmě pokud už nejsou pořešené), jejich vzdálenost od ''z'' nastavím jako ''d(z,v) := d(z,u) + e(u,v)''. Pokud nějaký soused (''v'') už je v haldě, tak se podívám, jestli cesta přes ''u'' není kratší než ta nastavená (''d(z,u) + e(u,v) < d(z,v)'') a případně udělám DECREASE. (Jestli je vrchol ''v'' haldě poznám tak, že má ''d(z,v) < ∞'', která tam nastavím na začázku; jestli už je pořešený poznám tak, že ''d(z,v) <= d(z,u)''.)
Dijkstra běží v O( (M + N) * log_d N ), v něterých případech to vyjde líp (viz skripta).
== Leftist haldy ==
Regulární haldy reprezentovaly jeden přístup k návrhům algoritmů na haldách, leftist haldy používají jiný, kterému se podobají i algoritmy binomiálních a Fibonacciho hald.
Regulární haldy byly postaveny kolem operací UP a DOWN, leftist haldy ovšem používají "rekurzivnější" přístup a jsou postaveny kolem operací MERGE a DECREASE. INSERT je pak prostě MERGE s jednoprvkovou haldou, DELETEMIN zase MERGE obou synů kořene, atd.
Zároveň máme jinou strukturální podmínku - místo pečlivého "vyplňování trojúhelníku" jako u regulárních hald jsme podstatně línější. U každého vrcholu si budeme pamatovat ''npl(v)'' (něco jako Nearest Path to Leaf) - nejkratší délku cesty "dolů" do vrcholu s nejvýše jedním synem. Leftist halda je pak binární strom, ve kterém platí:
* Když má vrchol jednoho syna, pak je to levý syn
* Když má vrchol dva syny, tak <math>npl(levý) \geq npl(pravý)</math>
* Strom má haldové uspořádání (hodnota vrcholu není menší, než hodnota předka)
Dá se dokázat, že v takovém případě délka nejdelší ''pravé cesty'' (tedy té směrem k menším npl) z nějakého vrcholu je omezena logaritmem počtu prvků v podstromu toho vrcholu (pravá cesta logicky končí ve vrcholu, který nemá pravého syna - buď má jen levého syna, nebo je to list).
=== MERGE ===
Vstupem funkce jsou dvě leftist haldy T1, T2.
* pokud T1 je prázdná, vrať T2
* pokud T2 je prázdná, vrať T1
* pokud kořen(T1) > kořen(T2), zaměň T1, T2
* T = MERGE(pravý podstrom T1, T2) , připoj T jako pravý podstrom k T1
* pokud npl(T1.levý) < npl(T1.pravý) prohoď pravého a levého syna T1
* npl(T1) = npl(T1.pravý) + 1; vrať T1;
MERGE "se pošle" na pravý podstrom, a pokud by ten moc vyrostl, tak podstromy prohodí. No a právě díky tomu, že pošleme MERGE rekurzí do pravých stromů, dosáhneme logaritmické časové složitosti.
=== INCREASE, DECREASE, DELETE ===
Při odstranění vrcholu ''v'' můžeme odstranit podstrom s kořenem ''v'', opravit zbytek stromu na leftist haldu a pak zase přimergeovat levý a pravý podstrom ''v''. Při odebrání uzlu se může zmenšit npl předka, což může vadit, pokud je uzel v jeho levém podstromě. Bylo by potřeba tuto haldu "opravit".
'''Oprav T, v''' : upraví T tak, aby po odtržení ''v'' nám zbyla validní halda.
* t = otec v; npl(t) = 0;
* pokud v je levý syn, prohoď ho s pravým synem, odpoj "v" od stromu
* dokud se zmenšuje npl(t):
** t = otec t;
** pokud npl(t.levý) < npl(t.pravý) prohoď levý a pravý
** npl(t) = npl(t.pravý) + 1
Ještě si musíme rozmyslet, že OPRAV bude trvat nejvíce O(logN). Úvaha je taková, že npl se mění jen dokud stoupáme po pravé cestě - jakmile jsme přišli zleva, npl pravého sourozence už je menší a zastavíme se. A pravá cesta má logaritmickou délku.
'''DECREASE v, z''' : hodnotu ''v'' zmenšíme o ''z'', T = Oprav(T, v), MERGE(T, podstrom s kořenem v).
'''INCREASE v, z''' : hodnotu ''v'' zvětšíme o ''z'', T = Oprav(T, v), levý podstrom ''v'', pravý podstrom ''v'' a samotné {v} přimergujeme k T.
'''DELETE v''' : T = Oprav(T, v), levý podstrom ''v'' a pravý podstrom ''v'' přimergujeme k T.
=== MAKEHEAP ===
'''MAKEHEAP S''' : vyrobí leftist haldu z pole S
* pro každé ''s'' z ''S'': přidej jednoprvkovou haldu {s} do fronty
* dokud fronta má aspoň 2 prvky: vyndám je, zmerguju a přidám na konec fronty // na konci ve frontě zbyde 1 halda pro celé S
'''Věta''' : MAKEHEAP běží v lineárním čase.
'''Důkaz''' : uvažujme "první" zpracování fronty s ''n'' haldami velikosti 1, druhé s n/2 haldami velikosti 2, ... k-té s <math>\frac{n}{2^k}</math> haldami velikosti <math>2^k</math>. MERGE funguje v O(log n), haldu s <math>2^k</math> prvky spojí v čase ''k''.
* <math>O \left( \sum_{k=0}^{\infty} \frac{n}{2^k} \cdot k \right) = O \left( n \cdot \sum_{k=0}^{\infty} \frac{k}{2^k} \right) = O \left( n \cdot c \right) = O \left( n \right)</math>
