Halda

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é)