4.3 Operace na Haldě

Binární minimová halda – Formalizace

Atributy haldy H

H.root, který je aktuální kořen
H.n, který udržuje aktuální počet prvků
H.last, který udržuje ukazatel na aktuální poslední list (nejpravější list v poslední hladině), pokud existuje

Prvek haldy $x$

klíč $k (x)$
ukazatel na otce
ukazatele na své syny (jsou-li v haldě obsažené)

V následujícím textu předpokládáme, že výše uvedené proměnné máme a umíme je přepočítat v čase $O (1)$ . Na závěr takovou implementaci předvedeme.

Algoritmus 4.1 (HeapInsert)

Algoritmus HeapInsert

Vložení prvku do haldy HeapInsert( $H, k$ )

Vstup

Halda $H$ .
klíč $k$ přidávaného prvku

Výstup

Halda $H$ s přidaným prvkem $p$ s klíčem $k$

Idea

Vlastnost Tvar haldy dovoluje přidat okamžitě nový prvek na konec nejspodnější hladiny
Pokud by již byla plná, založíme novou hladinu.
Pokud je Haldové uspořádání mezi novým listem l a jeho otcem o v pořádku, můžeme skončit.
Pokud ne, prohodíme $k (l)$ a $k (o)$ .
Tím se ale může porušit vlastnost Haldového uspořádání mezi vrcholem $o$ a otcem vrcholu $o$ .
Pokud pro ně Haldové uspořádání neplatí, opět jejich klíče prohodíme, jinak končíme.
Toto opakujeme, nejdále však až do kořene.

Algoritmus

Algoritmus HeapInsert(H,k):

HeapInsert(H, k)
    H.n += 1
    vlož na první volnou pozici v poslední hladině H
        nový vrchol p s klíčem k
    BubbleUp(H,p)

BubbleUp(H, p)
    Dokud p ̸= H.root:
        o := otec(p)
        Pokud k(o) ≤ k(p):
            return
        prohoď k(o) a k(p)
        p := o

Časová složitost

Na každé hladině strávíme $O (1)$ operací a procházených hladin je nejvýše logaritmicky mnoho, celkem tedy čas $O (l o g (n))$

Věta 4.3 (O koreknosti HeapInsert)

O koreknosti HeapInsert

Buď $H$ minimová halda a $k$ klíč. Potom struktura vzniklá voláním
HeapInsert( $H$ , $k$ ) je opět minimová halda.

Důkaz Věty 4.3

Pokud H je prázdná, pak je výsledkem jednoprvková halda – hotovo.
Jinak označme $H^{'}$ výsledek volání HeapInsert( $H$ , $k$ ).
$H^{'}$ má dle (3) tvar haldy.
Zbývá ověřit, že splňuje podmínku haldového uspořádání
Po přidání hodnoty $k$ do nového listu $l$ může existovat jen jedna hrana $s$ porušenou podmínkou. Tento problém pomocí funkce BubbleUp posouváme směrem ke kořeni.
Je třeba ověřit, že nemůžeme porušit podmínku haldového uspořádání mezi nějakým otcem $o$ a jeho (případným) druhým synem na cestě z $l$ do kořene.
- Pozorujeme, že hodnota $k (o)$ v $o$ se aplikováním BubbleUp nemohla zvýšit (může klesnout, případně zůstat stejná, pokud otec vrcholu $o$ měl stejnou hodnotu).

Algoritmus 4.2 (HeapExtractMin)

Algoritmus HeapExtractMin

Nalezení minima HeapFindMin( $H$ ) je triviální -> Vrátíme klíč kořene haldu v čase $O (1)$
HeapExtractMin(H) je komplikovanější: Odstranění kořene r = H.root stromu haldy by porušilo vlastnost tvar haldy.
Nicméně je možné triviálně odstranit poslední list $l$ , čili list nejvíc vpravo v poslední hladině.

Odstranění minima z haldy HeapExtractMin( $H$ )

Vstup

Halda $H$ .

Výstup

Halda $H$ s odebraným prvkem $p$ s nejmenším klíčem $k$

Idea

Prohoď $k (r)$ a $k (l)$
Odstraň vrchol $l$ a zmenši haldu o 1 prvek.
"Probublávej dolů" z kořene klíč $k (l)$ na jeho správné místo, aby opět platilo haldové uspořádání.

Algoritmus

Algoritmus HeapExtractMin(H):

Algoritmus HeapExtractMin(H)
    r = H.root, x = k(r), l = H.last
    prohoď k(r) a k(l)
    H.n := H.n − 1
    BubbleDown(r)
    return x


BubbleDown(v)
    Dokud má v nějaké syny:
        s := takový syn v, který má nejmenší klíč
        Pokud k(v) ≤ k(s):
            return
        prohoď k(v) a k(s)
        v := s

Časová složitost

Na každé hladině strávíme $O (1)$ operací a procházených hladin je nejvýše logaritmicky mnoho, celkem tedy čas $O (l o g (n))$

Věta 4.4 (O koreknosti HeapExtractMin)

O koreknosti HeapExtractMin

Buď $H$ minimová halda a $k$ klíč. Potom struktura vzniklá voláním
HeapExtractMin( $H$ ) je opět minimová halda.

Důkaz Věty 4.4

Tvar haldy je opět zachován triviálně.
Pokud je výsledkem prázdná či jednoprvková halda, máme hotovo
Prohození z řádku 3 mohlo porušit haldové uspořádání (mezi hladinami 0 a 1).
Opět prohazujeme s menším ze synů, čímž posunujeme porušení na dvojici následujících hladin.
Toto může pokračovat jen do poslední hladiny.

K Zamyšlení

Co se změní, když místo minimové haldy budeme pracovat s maximovou haldou a místo operací HeapExtractMin a HeapFindMin budeme tedy podporovat operace HeapExtractMax a HeapFindMax?
Rozmyslete algoritmus operace HeapChangeKey, která dostane ukazatel na prvek uložený v haldě, ve kterém se má klíč změnit na zadanou hodnotu tak, aby výsledkem byla opět halda.
Využitím operace HeapChangeKey lze definovat operaci, která umožňuje z haldy odstranit libovolný prvek zadaný ukazatelem. Popište její algoritmus.