Halda (heap)

Halda je stromová dátová štruktúra, ktorá spĺňa dve podmienky:

Lokálnu podmienku na usporiadanie (tzv. vlastnosť haldy), ktorá vyžaduje, aby pre každý vrchol stromu platilo, že hodnota kľúča v tomto vrchole je menšia ako hodnoty kľúčov jeho potomkov. Zápis lokálnej podmienky je: ak B je potomok A, tak potom key(A) >= key(B). Takéto haldy sa volajú max heaps. Ak otočíme podmienku a v koreňovom vrchole bude najmenší prvok, dostávame min heap.

Štrukturálnu podmienku na to, ako strom vyzerá - líši sa podľa jednotlivých typov. Budeme sa zaoberať binárnou haldou. Tá je reprezentovaná úplným (až na poslednú úroveň, kde je úplný zľava) binárnym stromom.

Haldy sa používajú na implementáciu prioritných frontov. Ich efektívnosť je taktiež veľmi dôležitá pre mnoho algoritmov na grafoch. Najznámejšie využitie haldy je v triediacom algoritme Heapsort

^ TOP

Reprezentácia haldy

Haldu budeme reprezentovať v poli A. Každý uzol stromu korešponduje s prvkom poľa, ktorý uchováva hodnotu tohto uzla. Pole A je objekt s dvoma atribútami: length[A], čo je celkový počet prvkov v poli a heap-size[A], čo je počet prvkov haldy uloženej v poli. Posledný prvok haldy v poli je teda A[heap-size[A]]. Koreňom stromu je prvok A[1]. Otcom i-teho uzla je prvok Parent(i), ľavým synom je prvok s indexom Left(i) a pravým synom je prvok s indexom Right(i). Tieto funkcie sa počítajú nasledovne:
 a) Parent(i) = spodná celá časť z (i/2)
 b) Left(i) = 2i
 c) Right(i) = 2i + 1

^ TOP

Operácie na halde

Časté operácie na halde sú:
 a) delete-max (delete-min): odstráni sa najväčší prvok (a upraví podľa toho haldu)
 b) increase-key (decrease-key): zmení hodnotu kľúča a aj polohu vrcholu v rámci haldy
 c) insert: vloží do haldy nový prvok
 d) merge: spojí dve haldy do jednej, ktorá obsahuje vrcholy z oboch predchádzajúcich
 e) heapify: udržuje vlastnosť haldy
 f) build-heap: vytvorí z poľa prvkov haldu

^ TOP

Udržiavanie haldy (heapify)

Vstupom procedúry je pole A a index i tohto poľa. Ak je procedúra vyvolaná, predpokladá sa, že binárne stromy s koreňmi Left(i) a Right(i) sú haldy. Ale prvok A[i] môže mať menšiu hodnotu ako jeho potomkovia, čo porušuje vlastnosť haldy. Preto Heapify premiestňuje hodnotu v A[i] na také miesto, aby podstrom s koreňom i zostal haldou.
Procedúra funguje tak, že v každom kroku je určený najväčší prvok z A[i], A[Left(i)] a A[Right(i)] a jeho index je uložený do premennej largest. Ak je hodnota A[i] najväčšia, potom podstrom s koreňom v uzle i je halda a procedúra končí. Ak nie, najväčšiu hodnotu má jeden zo synov, a preto je A[i] vymenená za A[largest], čo spôsobí, že uzol i (spolu s jeho synmi) bude spĺňať vlastnosť haldy. Uzol largest má teraz pôvodnú hodnotu A[i] a podstrom s týmto koreňom môže porušovať vlastnosť haldy. Preto sa pre tento podstrom vyvolá rekurzívne procedúra Heapify.
Čas behu procedúry heapify je O(h), kde h je výška haldy.

    Heapify(A,i)
    l := Left(i)
    r := Right(i)
    if (l <= heap-siZe[A]) and (A[l] > A[i])
      then largest := l
      else largest := i
    if (r <= heap-size[A]) and (A[r] > A[largest])
      then largest := r
    if largest != i then
      exchange (A[i],A[largest])
      Heapify(A,largest)      
      

^ TOP

Vytváranie haldy (build-heap)

Pre vytvorenie haldy z poľa použijeme procedúru Heapify. Všetky prvky v podpoli A[(n/2+1)..n] sú listy a každý z nich tvorí jednoprvkovú haldu. Procedúra Heapify postupne prechádza zvyšné uzly a na každom vykonáva operáciu Heapify. Poradie prechodu uzlami zabezpečuje, že sa Heapify vždy vykonáva na uzle, ktorého synovia sú už haldy.
Z neusporiadaného poľa sme schopní vytvoriť haldu v lineárnom čase.

    Build-Heap(A)
    heap-size[A] := length[A]
    for i := length[A] div 2 downto 1 do
      Heapify(A,i)
      

^ TOP