Prioritní fronta

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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šší a náročnější jsou například implementace v netříděném poli nebo spojovém seznamu. V takovém případě je vložení otázkou konstantního času, ovšem vydání prvku s nejvyšší prioritou má časovou náročnost O(n).

Obvyklejší je efektivní implementace pomocí haldy, kde má zařazení prvku i vydání prvku s nejvyšší prioritou časovou náročnost O(\log n).

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).