Prioritní fronta

Verze z 28. 8. 2011, 16:54 (editovat) Tester (diskuse | příspěvky) ← Porovnání se starší verzí		Aktuální verze z 20. 2. 2014, 06:35 (editovat) (zrušit editaci) Acolade (diskuse | příspěvky) m (kategorizace)
(Není zobrazena 1 mezilehlá verze od 1 uživatele.)
Řá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}}
		+	[[Kategorie:fav-kiv-bzinf]]

---

Aktuální verze z 20. 2. 2014, 06:35

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

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