Přeskočit na obsah

Prioritní fronta

Z Wikipedie, otevřené encyklopedie

Prioritní fronta je abstraktní datový typ v informatice. K jeho prvkům se na rozdíl od prvků obyčejné fronty váže ještě priorita: Pokud mají prvky stejnou prioritu, opouští frontu v pořadí, v jakém do ní byly vloženy, ale prvek s vyšší prioritou prvky s nižší prioritou předběhne a jde na výstup dříve.

Setříděná fronta tedy nabízí přinejmenším následující dvě operace:

zařaď do fronty s udanou prioritou
přijímá jako vstup prvek a jeho prioritu a prvek s jeho prioritou zařadí do fronty
vydej nejstarší z prvků s nejvyšší prioritou
odstraní z fronty ten z prvků s nejvyšší prioritou, který je tam nejdéle, a vrátí ho jako svůj výstup

Někdy jsou implementovány i další funkce, například možnost zjistit prvek s nejvyšší prioritou bez toho, že by byl odstraněn.

Implementace

[editovat | editovat zdroj]

Prioritní frontu je možné implementovat různými způsoby. Jednodušší na naprogramování, ale náročnější na procesorový čas jsou implementace netříděným polem nebo spojovým seznamem. Taková řešení nabízejí vložení v konstantním čase, ovšem vydání prvku s nejvyšší prioritou má časovou náročnost .

Rozšířenější je implementace pomocí haldy, kde má zařazení i vydání prvku s nejvyšší prioritou časovou náročnost ; platí to např. pro binární nebo binomiální haldu. Zvláštním případem je Fibonacciho halda, operace vložení do ní má asymptotickou složitost a vydání z ní toho prvku, jenž má nejvyšší prioritu, amortizovanou časovou složitost .

Literatura

[editovat | editovat zdroj]
  • SEDGEWICK, Robert. Algoritmy v C. Překlad Jiří Gree. Praha: SoftPress, 2003. ISBN 80-86497-56-9. Kapitola Prioritní fronty a heapsort (třídění pomocí haldy).