Prioritní fronta

Verze z 28. 8. 2011, 16:54 (editovat) Tester (diskuse | příspěvky) ← Porovnání se starší verzí		Verze z 28. 8. 2011, 21:12 (editovat) (zrušit editaci) Tester (diskuse | příspěvky) (→Modifikovatelná prioritní fronta) Porovnání s novější verzí →
Řádka 29:		Řádka 29:
	Pokud proritu příliš neměníme, způsob 1 je výhodnější, ale paměťově náročnější		Pokud proritu příliš neměníme, způsob 1 je výhodnější, ale paměťově náročnější
		+
		+	{{fav-kiv-bzinf}}

---

Verze z 28. 8. 2011, 21:12

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

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)

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ší