Prioritní fronta
Z FAV wiki
Speciální případ ADT podobne jako zásobník a fronta, výběr odebere prvek s nejvyšší či nejnižší prioritou (maximová resp. minimová PF) Vkládat lze prvky s libovolnou prioritou.
Implementace: polem / spoj.seznamem
[editovat] Složitost podle přístupu:
Rozhraní
- vytvoření prázdný fronty
- test prázdné 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)
[editovat] Modifikovatelná prioritní fronta
Pomocí haldy, a
- 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
- 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ší
