{{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(1), DOWN je O(logN), z toho vyplývají ostatní složitosti - složité je jen MAKEHEAP, dá se dokázat, že je jen <math>O(d^2N)</math>.
Složitost pořádně. Aplikace.
== 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) - délku cesty k nejbližšímu synovi do vrcholu s max. jedním synem. Pak každý uzel má nejvýše dva syny: má-li jednoho syna, je vždy levý, má-li oba, pak levý je ten s vyšším npl. Toť vše.
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). No a právě díky tomu, že pošleme MERGE rekurzí do pravých stromů, dosáhneme logaritmické časové složitosti.
MERGE tedy otestuje, jestli se nemůže provést triviálně, jinak prohazuje prvky kdyby se porušila haldová podmínka, prohazuje syny kdyby se porušila npl podmínka, a rekurzivně sestupuje do pravého syna.
Jak na DECREASE? Utrháváním stromů! Jednoduše řečeno, utrhneme z haldy podstrom zmenšovaného vrcholu, zmenšíme hodnotu vrcholu a celý podstrom zase přimergujeme zpět. Podobně to uděláme při INCREASE (jen musíme po zvýšení hodnoty nejdříve znovu zmergovat vrchol s jeho syny) a DELETE (utrhneme podstrom a přimergujeme jen jeho syny).
Fajn, teď jen zbývá vyrobit efektivně utrhávání stromu - tato pomocná procedura se obvykle nazývá z nějakých důvodů OPRAV. Nejdříve v otci utrženého vrcholu vynulujeme npl (a pokud to byl levý vrchol, uděláme z pravého nový levý). A teď jediné, co musíme dělat, je stoupat vzhůru, kontrolovat npl podmínku a updatovat hodnoty npl; ve chvíli, kdy už jsme npl nezměnili, se zastavíme.
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.
