Co je to zásobník (v kontextu datových struktur)?

Hromádek (heap) je specializovaný strom, který se používá jako datová struktura. Hlavní vlastností hromádky je částečné uspořádání: pro každý vrchol platí, že hodnota rodičovského vrcholu je větší nebo rovna hodnotě kterékoli jeho potomků (max-heap) nebo menší nebo rovna (min-heap).

Klíčové vlastnosti:

• Binární strom: Obvykle je implementován jako binární strom, kde má každý uzel nejvýše dva potomky.
• Kompletní binární strom: Na všech úrovních, kromě možná poslední, je strom zcela zaplněn. Uzly na poslední úrovni jsou zaplněny zprava doleva. To umožňuje efektivní ukládání hromádky ve formě pole.
• Vlastnosti hromádky:
  • Max-heap: Hodnota každého uzlu je větší nebo rovna hodnotám jeho potomků. Největší prvek je vždy na vrcholu.
  • Min-heap: Hodnota každého uzlu je menší nebo rovna hodnotám jeho potomků. Nejmenší prvek je vždy na vrcholu.

Hlavní operace s hromádkou:

• Vložení prvku: Přidání nového prvku a zachování vlastnosti hromádky.
• Odstranění prvku: Odstranění kořenového prvku (maximálního nebo minimálního v závislosti na typu hromádky) a zachování vlastnosti hromádky.
• Vytvoření hromádky: Konstrukce hromádky z pole prvků.

Použití hromádky:

• Třídění: Algoritmus haldového třídění (Heapsort).
• Fronty s prioritou: Efektivní implementace front, kde jsou prvky zpracovávány podle priority.
• Vyhledávací algoritmy: Například hledání k-tého podle hodnoty prvku.
• Grafové algoritmy: Například Dijkstrův algoritmus.

Zobrazení hromádky v poli:

Protože je hromádka úplným binárním stromem, může být efektivně uložena v poli bez použití ukazatelů.

• Pokud je uzel na indexu i, jeho levý potomek je na indexu 2*i + 1.
• Jeho pravý potomek je na indexu 2*i + 2.
• Jeho rodič je na indexu (i - 1) / 2.

# Příklad zobrazení min-hromádky ve formě pole
heap_array = [10, 15, 20, 17, 25, 30]

# Kořen: heap_array[0] = 10
# Levý potomek kořene: heap_array[2*0 + 1] = heap_array[1] = 15
# Pravý potomek kořene: heap_array[2*0 + 2] = heap_array[2] = 20
# Rodič prvku na indexu 3 (17): heap_array[(3-1)//2] = heap_array[1] = 15