Skip to content

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):
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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(log(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):
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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(log(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.