Halda - Historie editací

Tomiksed: /* Vlastnosti */

2017-05-28T16:39:01Z

Vlastnosti

← Starší verze		Verze z 28. 5. 2017, 16:39
Řádka 23:		Řádka 23:

	Implementace na poli:		Implementace na poli:
−	Má-li prvek na indexu k v poli potomky, jsou na indexech 2k a 2k+1. Splněním doplňkového pravidla haldy v poli nebudou mezery, a pozice pro vložení prvku či výměnu prvku při mazání je na konci pole	+	Má-li prvek na indexu k v poli potomky, jsou na indexech 2k+1 a 2k+2. Splněním doplňkového pravidla haldy v poli nebudou mezery, a pozice pro vložení prvku či výměnu prvku při mazání je na konci pole

	Implementace objektově		Implementace objektově

Tomiksed: /* Vlastnosti */

2017-05-28T16:38:11Z

Vlastnosti

← Starší verze		Verze z 28. 5. 2017, 16:38
Řádka 23:		Řádka 23:

	Implementace na poli:		Implementace na poli:
−	Má-li prvek na indexu k v poli potomky, jsou na indexech 2k+1 a 2k+2. Splněním doplňkového pravidla haldy v poli nebudou mezery, a pozice pro vložení prvku či výměnu prvku při mazání je na konci pole	+	Má-li prvek na indexu k v poli potomky, jsou na indexech 2k a 2k+1. Splněním doplňkového pravidla haldy v poli nebudou mezery, a pozice pro vložení prvku či výměnu prvku při mazání je na konci pole

	Implementace objektově		Implementace objektově

Acolade: kategorizace

2014-02-20T06:36:41Z

kategorizace

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

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

Tester v 30. 8. 2011, 16:57

2011-08-30T16:57:30Z

← Starší verze		Verze z 30. 8. 2011, 16:57
Řádka 27:		Řádka 27:
	Implementace objektově		Implementace objektově
	Jako spojová struktura, je však nutné udržovat pointer na rodiče nejnižší úrovně (to může být problematické a pomalé)		Jako spojová struktura, je však nutné udržovat pointer na rodiče nejnižší úrovně (to může být problematické a pomalé)
		+
		+	{{fav-kiv-bzinf}}

81.201.60.162 v 9. 8. 2011, 17:28

2011-08-09T17:28:43Z

← Starší verze		Verze z 9. 8. 2011, 17:28
Řádka 1:		Řádka 1:
−	Halda je datová struktura, která má následující vlastnosti	+	Halda je datová struktura, která má následující vlastnosti:
−	~~Jde o strom~~	+
−	~~Pokud C je potomkem P, potom hodnota h(C) <= h(P)~~	+

−	Tato halda se nazývá MaxHeap, protože má v kořeni vždy větší prvek. Existuje také minHeap, které je seřazena opačně.	+	* Jde o strom
		+	* Pokud C je potomkem P, potom hodnota h(C) <= h(P)
		+
		+	Tato halda se nazývá MaxHeap (maximální halda), protože má v kořeni vždy větší prvek. Existuje také minHeap (minimální halda), které je seřazena opačně.
		+
		+
		+	== Implementace ==

	Nejjednodušší haldou může být seřazené pole či seznam. Nejčastěji se však používá binární halda, a pojmem halda tuto binární haldu většinou myslíme, existují však i další (binominální, Fibonacciho, měkká ...)		Nejjednodušší haldou může být seřazené pole či seznam. Nejčastěji se však používá binární halda, a pojmem halda tuto binární haldu většinou myslíme, existují však i další (binominální, Fibonacciho, měkká ...)

	Binární halda má ještě jednu vlastnost, vyváženost (vlastnost tvaru, úplnost stromu). Ta říká, že je halda buď vyvážená (všechny listy jsou na stejné úrovni h) a nebo je plněna zleva do prava.		Binární halda má ještě jednu vlastnost, vyváženost (vlastnost tvaru, úplnost stromu). Ta říká, že je halda buď vyvážená (všechny listy jsou na stejné úrovni h) a nebo je plněna zleva do prava.
		+
		+
		+	== Vlastnosti ==

	Vyhledání nejvyššího prvku v haldě je triviální (jde o kořen haldy, tedy O(1))		Vyhledání nejvyššího prvku v haldě je triviální (jde o kořen haldy, tedy O(1))

−	Vkládání prvku ~~probáhá~~ tak, že jej vložíme do nejnižší úrovně haldy, co nejvíce doleva. Pokud je porušena vlastnost haldy, vyměníme prvek s jeho rodičem a opakujeme, dokud není vlastnost haldy zcela obnovena.	+	Vkládání prvku probíhá tak, že jej vložíme do nejnižší úrovně haldy, co nejvíce doleva. Pokud je tímto porušena vlastnost haldy, vyměníme prvek s jeho rodičem a opakujeme, dokud není vlastnost haldy zcela obnovena.

	Mazání prvku je podobné. V binární haldě jej provádíme tak, že najdeme prvek, který je na nejnižší úrovni zcela vlevo (mimochodem, to se dá v poli zařídit indexem, v objektech ukazatelem), vyměníme jej s mazaným prvkem a obnovíme vlastnost haldy. Mazaný prvek z haldy po té samozřejmě vyjmeme.		Mazání prvku je podobné. V binární haldě jej provádíme tak, že najdeme prvek, který je na nejnižší úrovni zcela vlevo (mimochodem, to se dá v poli zařídit indexem, v objektech ukazatelem), vyměníme jej s mazaným prvkem a obnovíme vlastnost haldy. Mazaný prvek z haldy po té samozřejmě vyjmeme.

Tester: Založena nová stránka: Halda je datová struktura, která má následující vlastnosti Jde o strom Pokud C je potomkem P, potom hodnota h(C) <= h(P) Tato halda se nazývá MaxHeap, protože má...

2011-08-08T15:03:06Z

Založena nová stránka: Halda je datová struktura, která má následující vlastnosti Jde o strom Pokud C je potomkem P, potom hodnota h(C) <= h(P) Tato halda se nazývá MaxHeap, protože má...

Nová stránka

Halda je datová struktura, která má následující vlastnosti
Jde o strom
Pokud C je potomkem P, potom hodnota h(C) <= h(P)

Tato halda se nazývá MaxHeap, protože má v kořeni vždy větší prvek. Existuje také minHeap, které je seřazena opačně.

Nejjednodušší haldou může být seřazené pole či seznam. Nejčastěji se však používá binární halda, a pojmem halda tuto binární haldu většinou myslíme, existují však i další (binominální, Fibonacciho, měkká ...)

Binární halda má ještě jednu vlastnost, vyváženost (vlastnost tvaru, úplnost stromu). Ta říká, že je halda buď vyvážená (všechny listy jsou na stejné úrovni h) a nebo je plněna zleva do prava.

Vyhledání nejvyššího prvku v haldě je triviální (jde o kořen haldy, tedy O(1))

Vkládání prvku probáhá tak, že jej vložíme do nejnižší úrovně haldy, co nejvíce doleva. Pokud je porušena vlastnost haldy, vyměníme prvek s jeho rodičem a opakujeme, dokud není vlastnost haldy zcela obnovena.

Mazání prvku je podobné. V binární haldě jej provádíme tak, že najdeme prvek, který je na nejnižší úrovni zcela vlevo (mimochodem, to se dá v poli zařídit indexem, v objektech ukazatelem), vyměníme jej s mazaným prvkem a obnovíme vlastnost haldy. Mazaný prvek z haldy po té samozřejmě vyjmeme.

Implementace na poli:
Má-li prvek na indexu k v poli potomky, jsou na indexech 2k+1 a 2k+2. Splněním doplňkového pravidla haldy v poli nebudou mezery, a pozice pro vložení prvku či výměnu prvku při mazání je na konci pole

Implementace objektově
Jako spojová struktura, je však nutné udržovat pointer na rodiče nejnižší úrovně (to může být problematické a pomalé)