Čo je to halda?

Hromádek (heap) je špeciálna stromová dátová štruktúra, ktorá spĺňa vlastnosť hromádky. Táto vlastnosť hovorí, že pre každý vrchol, okrem koreňa, musí byť hodnota kľúča tohto vrcholu v určitej súvislosti s hodnotou kľúča jeho rodiča. Existujú dva hlavné typy hromádok:

• Max-hromádka (Max-heap): Hodnota kľúča každého vrcholu nie je menšia ako hodnota kľúčov jeho detí. Najväčší prvok je v koreňovej vrchole.
• Min-hromádka (Min-heap): Hodnota kľúča každého vrcholu nie je väčšia ako hodnota kľúčov jeho detí. Najmenší prvok je v koreňovej vrchole.

Hromádka je zvyčajne implementovaná ako pole, čo umožňuje efektívny prístup k prvkom a vykonávanie operácií. Vzťah medzi rodičmi a deťmi v poli je nasledovný:

• Pre prvok s indexom i (začínajúc od 0), jeho ľavý potomok je na indexe 2i + 1.
• Jeho pravý potomok je na indexe 2i + 2.
• Jeho rodič je na indexe floor((i - 1) / 2).

Hlavné operácie nad hromádou:

• Vloženie (Insert): Pridanie nového prvku. Časová zložitosť O(log n), kde n je počet prvkov.
• Extract-Max / Extract-Min: Odstránenie a vrátenie maximálneho (v max-hromádke) alebo minimálneho (v min-hromádke) prvku. Časová zložitosť O(log n).
• Heapify (Vytvorenie hromádky): Premena ľubovoľného poľa na hromádku. Časová zložitosť O(n).

Hromádky sa používajú v algoritmoch triedenia (napríklad heapsort), v prioritných frontoch a v algoritmoch hľadania najkratších ciest (napríklad Dijkstrův algoritmus).