Binární halda

Definice

Binární halda je datová struktura tvaru binárního stromu, která uchovává množinu n porovnatelných prvků splňující vlastnost haldy. Halda může být uspořádána vzestupně nebo sestupně a proto často rozlišujeme dva druhy hald, pro které platí trochu jiná vlastnost haldy:

  • Vlastnost minimové binární haldy (min-heap). Pro každý vrchol v a pro každého potomka t platí, platí k(v) ≤ k(t).
  • Vlastnost maximové binární halda (max-heap). Pro každý vrchol v a pro každého potomka t platí, platí k(v) ≥ k(t).

Vlastnost haldy je rekurzivní - všechny podstromy haldy jsou také haldy. Díky této vlastnosti máme garantováno, že se halda chová jako prioritní fronta - na vrcholek haldy vždy musí vystoupat prvek s nejvyšší prioritou.

Vlastnosti stromů

Věta

Binární halda s n prvky má ⌈n/2⌉ listů a ⌊n/2⌋ vnitřních vrcholů.

Důkaz

Indukcí podle počtu vrcholů binárního stromu.


Věta o hloubce haldy

Halda s n prvky má ⌊log2 n⌋ + 1 hladin.

Důkaz

Binární strom s h úplnými hladinami má n = 20+ 21 + 22 + ··· + 2h−1 = 2h−1 vrcholů. Vzhledem ke tvaru haldy přibude nová hladina jen tehdy, když počet prvků n vzroste na mocninu dvojky.

Operace

Operace: Složitost:
Vkládání: O(log n)
Najdi minimum/maximum: O(1)
Odstraň minimum/maximum: O(log n)
Build: O(n)

 

Funkce k(x) nám vrací klíč. n je velikost haldy.

Vkládání (insert)

Princip:
  1. Podmínka na tvar haldy nám dovoluje přidat nový list na konec poslední hladiny. Pokud by tato hladina byla plná, můžeme založit novou s jediným listem úplně vlevo.
  2. Pokud je haldové uspořádání mezi novým listem a jeho rodičem v pořádku, můžeme skončit.
  3. Pokud ne, prohodíme k(l) a k(o).
  4. Tím, ale může nastat problém mezi klíčem vrcholu o a klíčem otce vrcholuo, tj. nemusí pro ně platit haldové uspořádání.
  5. Pokud pro ně neplatí, opět jejich klíče prohodíme a opakujeme,atd., až nejdále do kořene.
Pseudokód:
Procedura HeapInsert(H, k)
Vstup: Nový prvek p s klíčem k
1. n := n+1
2. p(n) ← p, k(n) ← k # Vlož na první volnou pozici v poslední hladině H nový vrchol p
3. BubbleUp(p)

 

Bublání funguje stejně jako v BubbleSortu, akorát místo průchodu pole probubláváme podél cesty ve stromě vedoucí z uzlu v do kořene nebo do listu.

Procedura BubbleUp(p)
1. Dokud p není kořen:
2.  o := rodič(p) # ⌊i/2⌋
3.  Pokud k(o) ≤ k(p):
4.      vyskočíme z cyklu.
4.  Prohodíme k(p) s k(o)
5.  p := o
Analýza složitosti:

Časovou složitost odhadneme snadno: na každé hladině stromu strávíme nejvýše konstantní čas a hladin je logaritmický počet. Operace Insert tedy trvá O(log n).

 

Najdi minimum/maximum

Procedura HeapFindMin(p)
1. vratí klíč kořene r haldy

 

Nalezení a odstranění minima

Algoritmus HeapExtractMin(H)
    r = kořen, l = poslední list
    Prohoď k(r) a k(l)
    n := n−1
    BubbleDown(r)

 

Procedura BubbleDown(v)
    Dokud mávnějaké syny:
    s:= takový synv, který má nejmenší klíč
    Pokudk(v)≤k(s):
    return
    Prohoď k(v) a k(s)

Implementace

Vztahy indexů v haldě

Má-li vrchol v index i, pak

  • jeho levý potomek má index 2i a
  • pravý potomek index 2i + 1,
  • rodič má index ⌊i/2⌋ a
  • výraz i mod 2 udává, zda je v připojen k rodiči levou či pravou hranou, tj. zda je jeho levý či pravý potomek.

 

Binární haldy mohou být implementovány jednoduše pomocí pole nebo spojového seznamu. K implementaci je také možné použít datové struktury binárního stromu.

K zamyšlení

Je binární halda úplný binární strom?

Ne. Je téměř úplný binární strom. Neúplná může být pouze poslední vrstva listů a to ještě jen zprava. Určitě je vyvážený binární strom.

Související