{{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 $f\colon S \to \mathbb{R}$, 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*: $\forall x \in S: f(otec(x)) \le f(x)$. (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 $O(dN)$.

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 $npl(levý) \geq npl(pravý)$
* 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 $\frac{n}{2^k}$ haldami velikosti $2^k$. MERGE funguje v O(log n), haldu s $2^k$ prvky spojí v čase *k*.

* $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)$
