Co je to halda?

Hromádek (heap) je speciální stromová datová struktura, která splňuje vlastnost hromádkové struktury. Tato vlastnost říká, že pro každý vrchol, kromě kořene, musí být hodnota klíče tohoto vrcholu v určitém vztahu s hodnotou klíče jeho rodiče. Existují dva hlavní typy hromádek:

• Max-hromádek (Max-heap): Hodnota klíče každého vrcholu není menší než hodnota klíčů jeho dětí. Největší prvek je v kořeni.
• Min-hromádek (Min-heap): Hodnota klíče každého vrcholu není větší než hodnota klíčů jeho dětí. Nejmenší prvek je v kořeni.

Hromádek je obvykle implementován jako pole, což umožňuje efektivní přístup k prvkům a provádění operací. Vztah mezi rodiči a dětmi v poli je následující:

• Pro prvek s indexem i (počínaje od 0), jeho levý potomek je na indexu 2i + 1.
• Jeho pravý potomek je na indexu 2i + 2.
• Jeho rodič je na indexu floor((i - 1) / 2).

Hlavní operace nad hromádkem:

• Vložení (Insert): Přidání nového prvku. Časová složitost O(log n), kde n je počet prvků.
• Extract-Max / Extract-Min: Odstranění a vrácení maximálního (v max-hromádce) nebo minimálního (v min-hromádce) prvku. Časová složitost O(log n).
• Heapify (Vytvoření hromádky): Převod libovolného pole na hromádku. Časová složitost O(n).

Hromádky se používají v algoritmech třídění (například heapsort), v prioritních frontách a v algoritmech hledání nejkratších cest (například Dijkstrův algoritmus).