Halda
(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á...) |
m (→Vlastnosti) |
||
| (Nejsou zobrazeny 4 mezilehlé verze od 4 uživatelů.) | |||
| Řádka 1: | Řádka 1: | ||
| − | Halda je datová struktura, která má následující vlastnosti | + | Halda je datová struktura, která má následující vlastnosti: |
| − | + | ||
| − | + | ||
| − | 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 | + | 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. | ||
| Řádka 20: | Řá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}} | ||
| + | [[Kategorie:fav-kiv-bzinf]] | ||
Aktuální verze z 28. 5. 2017, 16:39
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 (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ě.
[editovat] 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á ...)
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.
[editovat] Vlastnosti
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 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.
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é)
