Prioritní fronta - Historie editací

Acolade: kategorizace

2014-02-20T06:35:57Z

kategorizace

← Starší verze		Verze z 20. 2. 2014, 06:35
Řádka 31:		Řádka 31:

	{{fav-kiv-bzinf}}		{{fav-kiv-bzinf}}
		+	[[Kategorie:fav-kiv-bzinf]]

Tester: /* Modifikovatelná prioritní fronta */

2011-08-28T21:12:25Z

Modifikovatelná prioritní fronta

← Starší verze		Verze z 28. 8. 2011, 21:12
Řá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}}

Tester v 28. 8. 2011, 16:54

2011-08-28T16:54:43Z

← Starší verze		Verze z 28. 8. 2011, 16:54
Řádka 1:		Řádka 1:
−	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.	+	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:	+	'''Implementace:''' polem / spoj.seznamem
		+
		+
		+	== Složitost podle přístupu: ==

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

−	Lazy:	+	'''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)		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:	+
		+	'''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)		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:	+
		+	'''Kombinace:'''
	Implementace pomocí BVS nebo haldy - vložení i výber O(log2n)		Implementace pomocí BVS nebo haldy - vložení i výber O(log2n)

−	Modifikovatelná prioritní fronta	+
		+	== Modifikovatelná prioritní fronta ==
		+
	Pomocí haldy, a		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	+	# 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)	+	# 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ší		Pokud proritu příliš neměníme, způsob 1 je výhodnější, ale paměťově náročnější

Tester: Založena nová stránka: 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 li...

2011-08-08T15:02:52Z

Založena nová stránka: 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 li...

Nová stránka

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