Prioritný front

Prioritný front je dátová štruktúra pre uchovávanie množiny S prvkov, z ktorých každý má priradenú špeciálnu hodnotu – kľúč.
Prioritný front podporuje nasledovné operácie:
 a) Insert(S,x) – vloží prvok x do množiny S
 b) Maximum(S) – vráti prvok S s najväčšou hodnotou kľúča
 c) Extract-Max(S) – vráti prvok S s najväčšou hodnotou kľúča a odstráni ho z množiny S

Prioritný front sa používa napríklad na plánovanie činností na zdieľanom počítači. Prioritný front udržiava prehľad o činnostiach, ktoré sa majú vykonať a o ich prioritách. Ak sa nejaká činnosť skončí, alebo preruší, vyberie sa ďalšia činnosť s najvyššou prioritou pomocou Extract-Max. Nová činnosť sa vkladá použitím Insert.

^ TOP

Implementácia

Na implementáciu prioritného frontu je možné použiť haldu. Tá umožnuje, že na množine n prvkov bude časová zložitosť operácií najviac O(lg n).
Operácia Heap-Maximum vráti najväčší prvok v konštantnom čase – vráti hodnotu A[1] z haldy.
Procedúra Heap-Extract-Max je podobná telu cyklu for procedúry Heapsort. Čas behu Heap-Extract-Max je O(lg n), keďže vykonáva len o konštantné množstvo operácií viac ako Heapify.
Procedúra Heap-Insert vkladá do haldy A nový uzol. Rozšíri haldu pridaním nového listu do stromu a prechádza od tohto miesta smerom ku koreňu kým nenájde správne miesto na vloženie. Čas behu tejto procedúry je O(lg n).

    Heap-Extract-Max
    if (heap-size[A] < 1) then
      error "heap underflow"
    max := A[1]
    A[1] := A[heap-size[A]]-1
    Heapify(A,1)
    return max
    
    Heap-Insert(A,key)
    heap-size[A] := heap-size[A]+1
    i := heap-size[A]
    while (i > 1) and (A[Parent(i) < key]) do
      A[i] := A[Parent(i)]
      i := Parent(i)
    A[i] := key      
      
      

^ TOP