Prioritní fronta
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
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
- 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).