Prioritní fronta

Speciální prípad ADT podobne jako zásobník a fronta, výber odebere prvek s nejvyšší ci nejnižší prioritou (maximová resp. minimová PF) Vkládat lze prvky s libovolnou prioritou.

Implementace polem / spoj.seznamem. Složitost podle přístupu:

Rozhraní vytvoření rpázdný fronty test prázdfné fronty vložení a výběr prvku

Lazy: Pole či seznam je neuspořádaný, vkládáme prvek vždy na konec v poli (O(1)) a na začátek v seznamu (O(1)). Při výběru musíme najít maximum, v obou případech O(n) Eager: Pole či seznam je uspořádaný, prvek vkládáme tak, aby byla struktura seřazena. Vložení je O(n), ale výběr je O(1) (ze začátku seznamu / konce pole) Kombinace: Implementace pomocí BVS nebo haldy - vložení i výber O(log2n)

Modifikovatelná prioritní fronta Pomocí haldy, a 1) Přidáme mapu prvek->pozice v haldě. Změnou priority a obnovením haldy je možné v O(log2n) prioritu i měnit 2) Bez mapy je hledání prvku v haldě další O(log2n) čas, celkem tedy hledání O(log2n) + obnovení haldy O(log2n)

Pokud proritu příliš neměníme, způsob 1 je výhodnější, ale paměťově náročnější