Často potřebujeme přístup k informacím, tak aby tyto byly seřazeny podle hodnot klíče, avšak ne najednou ke všem, ale z času na čas potřebujeme vybrat záznam s nejvyšší (nejnižší) hodnotou klíče. Navíc mezi jednotlivými výběry mohou být vloženy další záznamy. Příkladem jsou výpočetní systémy, kde požadavky na přidělení procesoru jsou typicky obsluhovány podle svých priorit. Když se procesor stane volným, přidělí se úloze s nejvyšší prioritou. Během jejího výpočtu mohou přijít další úlohy a když její výpočet skončí vybere se opět úloha s aktuálně nejvyšší prioritou, atd. Odpovídající abstraktní datový typ, tedy musí poskytovat operace vlož prvek a vyber největší prvek. Takový ADT budeme nazývat prioritní frontou. Situace je podobná jako u fronty a zásobníku, kde také je blíže specifikována operace vyber - vyber poslední vložený a vyber první vložený prvek. Kromě použití v aplikacích, které mají uvedený charakter, prioritní fronta se používá také v některých složitějších algoritmech, např. grafových. Libovolnou prioritní frontu můžeme použít na seřazení jejich prvků. Opakováním výběru největšího prvku, získáme jejich sestupné seřazení. Dále se budeme zabývat implementací prioritní fronty.
Rozhraní ADT prioritní fronta obsahující prvky, které jsou objekty třídy Prvek je definováno následovně
class PF {
// ADT rozhrani
PF( ); // vytvoření prázdné prioritní fronty
boolean jePrazdna( ); // test, je-li prázdná
void vloz(Prvek); // vložení prvku
Prvek vybermax( ); // výběr největšího prvku
}
Tak jako v případě zásobníku a fronty, některé algoritmy skončí, když je prioritní fronta prázdná na co slouží metoda jePrazdna( ). Pro operaci výběru prvku slouží metoda vybermax( ) a tedy vybírán je největší prvek. Pro některé aplikace je vhodnější vybírat z prioritní fronty prvek s nejmenší hodnotou a odpovídající metoda by měla název vybermin( ). Takovou prioritní frontu budeme nazývat minimovou prioritní frontou. Pokud prioritní frontu blíže nespecifikujeme budeme mít na mysli prioritní frontu s výběrem největšího prvku ve smyslu běžného rčení vysoká priorita.
Někdy může být vhodné rozšířit rozhraní ADT prioritní fronta o další operace, např. nalezení největšího prvku, obdobně jako jsme zavedli operaci top pro zásobník namísto dvojice operací pop a push.
Elementární implementace ADT prioritní fronta mohou obdobně jako zásobník a fronta použít pole nebo spojový seznam.
Prvky prioritní fronty můžeme uchovávat v uspořádaném poli, kdy operace výběru prvku, přímo odebere největší prvek z konce pole, ale vložení prvku musí zachovat uspořádaní. Program na obr.
implementuje prioritní frontu pomocí uspořádaného pole pro celá čísla.
Operace odebrání maxima se vykoná v konstantním čase. Vkládaní, je založeno na myšlence vložení prvku na konec seřazené fronty a jeho postupnou výměnnou s prvky před ním dokud prvek před ním je větší, čím se nalezne pozice kam vkládaný prvek patří. Stejná myšlenka byla použita v algoritmu řazení vkládáním, kde se postupně každý prvek vložil na správné místo do podposloupnosti uspořádaných prvků před ním. V nejhorším případě nutno projít všechny prvky v prioritní frontě.
Alternativně můžeme prioritní frontu implementovat neuspořádaným polem, kdy nevětší prvek budeme hledat až při jeho vybíraní. Tento přístup implementuje program na obr.
.
V tomto případě operace vložení prvku má konstantní čas, kdežto operace výběru největšího prvku v nejhorším případě potřebuje projít všechny prvky pole.
Prvky prioritní fronty můžeme uchovávat pomocí spojového seznamu, se stejnými dopady, jako má rozhodnutí o implementaci zásobníku a fronty pomocí pole nebo spojového seznamu.
Prvky ve spojovém seznamu můžeme opět udržovat seřazené nebo neuspořádané. Pro ilustraci uvedeme, implementaci prioritní fronty pomocí neuspořádaného spojového seznamu (obr.
a 
).
Při implementaci pomocí pole jsme vkládali a vybírali prvek na konci pole, bez ohledu na to bylo-li pole uspořádané nebo ne. Při implementaci neuspořádaným obousměrným spojovým seznamem, prvek vkládáme na jeho začátek a největší prvek po jeho nalezení přímo odebereme. Implementace pomocí uspořádaného spojového seznamu by odebírala prvek ze začátku seznamu a pro jeho vložení musí nalézt místo pro vložení. Časová náročnost operací vložení a výběru největšího prvku je v nejhorším případě pro implementaci spojovým seznamem stejná jako pro implementaci pomocí pole.
Uchovávaní prvků prioritní fronty jako neuspořádané posloupnosti je příkladem tzv. trpělivého (lazy) přístupu k řešení problému implementace její operací, kdy to co v rámci dané operace nemusíme udělat odložíme na později. Na druhé straně, uchovávaní prvků prioritní fronty jako uspořádané posloupnosti je příkladem tzv. netrpělivého (eager) přístupu k řešení problému, kdy v rámci operace vykonáme co nejvíce práce potřebné pro efektivní implementaci jiných operací.
Z uvedených vlastností implementace operací vlož a vyber největší prvek pro nejhorší případ, můžeme charakteristiku časové náročnost některých operací ADT prioritní fronta shrnout do tabulky na obr.
Vidíme, že uvedené implementace jsou efektivní buď pro operaci vložení prvku nebo pro operace výběru a nalezení největšího prvku v prioritní frontě. Výslední efektivnost klientského programu, potom bude významně záviset na tom v jakém poměru bude používat uvedené operace. Bude-li například operace nalezení největšího prvku hodně častější než vložení může být uspořádaný seznam nebo pole vhodnou implementací.
Efektivním uložením prvků dynamické množiny uvažující velikost klíčů byl BVS, kde operace vložení a nalezení prvku se zadaným klíčem byly O(h), kde h je výška stromu. V případě ADT prioritní fronta je operace výběru prvku specifikována jako výběr prvku s největším nebo s nejmenším klíčem.
Připomeňme, že prvek v BVS s největším klíčem nalezneme tak, že budeme z kořene sledovat pořád ukazatele na pravý podstrom až k listu, kde ukazatel je null. Vzhledem k vlastnosti BVS, nemá-li vrchol x pravý podstrom, protože v levém podstromu jsou prvky s menším klíčem než x.klic, je x prvek s největším klíčem. Má-li x pravý podstrom, potom, protože v levém podstromu jsou klíče menší než x.klic, prvek s největším klíčem musí být v pravém podstromu s kořenem x.pravy. Metoda maxKlic( ) pro nalezení největšího klíče BVS je na obr.
. Odebrání prvku s největším klíčem je specielním případem vybrání prvku ze stromu. Je-li tímto prvkem kořen BVS znamená to, že kořenem BVS se stane levý následník, jinak ukazatel na pravého následníka v předchůdci vrcholu s největším klíčem se stane null. Odpovídající metoda
vyberMax( ) je na obr.. Situace pro nejmenší prvek je symetrická.
Pro implementaci prioritní fronty pomocí BVS nyní máme operace vložení, nalezení i výběru největšího prvku O(h). Víme již, že výška BVS je v nejhorším případě n -1. Obecně však je v průměrném případě 1,39log2n, tedy lepší než n /2 pro pole nebo seznam. V průměrném případě půjde při implementaci pomocí BVS o zlepšení těch operací, kterých časová náročnost je v nejhorším případě n při implementaci pomocí pole nebo seznamu.
Na druhé straně, n prvků můžeme uložit ve stromě s výškou Θ(log2 n) zaplňujeme-li postupně jednotlivé úrovně počínaje kořenem. Takové stromy budeme nazývat úplné. Navíc potřebujeme, aby uložení prvků ve stromě zohledňovalo velikosti jejich klíčů tak, aby bylo možno efektivně určit prvek s největším klíčem. Takovou strukturou je halda, kterou se budeme zabývat v článku 8.2.