Motivace: V počítači je fronta úloh čekajících na zpracování. Čekající úlohy “sedí” v paměti v dlouhé řadě židlí, které běžně říkáme pole. Pokud přibude nová úloha, tak se posadí na židli na konci fronty. Pan Procesor úlohy postupně zpracovává. Když řekne “další pán na holení”, tak si vyzvedne úlohu na začátku fronty. Takhle funguje obyčejná fronta. Na její realizaci není nic složitého.1

Co když se ale přižene systémová úloha, která začne tvrdit, že je důležitější než ostatní úlohy, a začne předbíhat ve frontě? Pokud budeme chtít důležitější úlohy upřednostnit, tak každé úloze přiřadíme její prioritu. Představme si ji jako číselnou hodnotu. Úloha s vyšší prioritou může předběhnout všechny úlohy nižší prioritou.

Jak ale teď bude fungovat vyzvedávání úlohy, která je na řadě (má nejvyšší prioritu)? A kam posadíme nově příchozí úlohy? Frontu můžeme v poli udržovat setříděnou podle priorit. Odebrání úlohy, která je na řadě, se nebude lišit od obyčejné fronty. Odebereme první prvek pole. Pro přidání nové úlohy musíme nejprve přesadit úlohy s nižší prioritou o jedno místo zpátky a tím si vytvořit volnou židli pro nově příchozí úlohu. To ovšem vyžaduje až $\OO(n)$ přesazování.

Navrhněte systém fungování prioritní fronty tak, aby přidání nové úlohy a i odebrání úlohy s nejvyšší prioritou, fungovalo co nejefektivněji. To je abychom museli přesadit co nejméně úloh. Není nutné, aby byly úlohy v poli seřazeny podle priority.

Úkol: Obyčejná fronta je seznam prvků seřazený podle času příchodu. Prioritní fronta je seznam prvků seřazený podle priorit. Každý prvek má svojí hodnotu, tzv. prioritu. Prvky s vyšší prioritou mohou ve frontě předběhnout prvky s nižší prioritou. Pokud mají dva prvky stejnou prioritu, tak jsou seřazeny podle času příchodu.

Pro práci s prioritní frontou potřebujeme umět odebrat prvek, který je na řadě (ten s nejvyšší prioritou), přidávat a mazat prvky a také u některých prvků měnit prioritu. A to vše co nejefektivněji.

Pro jednoduchost předpokládejme, že vyšší priorita odpovídá nižší číselné hodnotě. Prvky s nejvyšší prioritou jsou tedy ty s nejnižší číselnou hodnotou.2

Řešení pomocí pole:

V tomto řešení je $\ARRAY{x}{\cdot}$ neuspořádané pole. Nemusíme nic vytvářet. Operace nalezení minima spočívá v průchodu pole a trvá čas $\OO(n)$. Ostatní operace lze realizovat v konstantním čase.

Použitím setříděného pole si moc nepomůžeme. Zkuste se zamyslet nad realizací a časovou složitostí jednotlivých operací. Dostaneme horší výsledek než při použití haldy.

Řešení pomocí haldy:

Použijeme haldu, kde klíčem uzlů/úloh bude jejich priorita. Operace požadované po prioritní frontě přímo odpovídají operacím pro práci s haldou. Například odebrání prvku s nejvyšší prioritou zajistí funkce MIN a DELMIN, změnu priority funkce INCREASEKEY a DECREASEKEY apod. Časová složitost operací je $\OO(\log n)$.