TIN066 Základní haldy

Z ωικι.matfyz.cz
Přejít na: navigace, hledání

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é uspořádání; takhle napsaná platí pro min-heap, může se definovat i opačně, pak dostaneme max-heap.)

Tato část je neúplná a potřebuje rozšířit. 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) $
Citováno z „http://wiki.matfyz.cz/index.php?title=TIN066_Základní_haldy&oldid=21187“