Čo je zásobník (v kontexte dátových štruktúr)?

Hromada (heap) — je špecializované stromové dátové štruktúra, ktorá sa používa ako dátová štruktúra. Hlavnou vlastnosťou hromady je čiastočná usporiadanosť: pre každý vrchol stromu platí, že hodnota rodičovského vrcholu je väčšia alebo rovná hodnote ktoréhokoľvek z jeho detí (max-hromada) alebo je menšia alebo rovná (min-hromada).

Kľúčové vlastnosti:

• Binárny strom: Najčastejšie sa implementuje ako binárny strom, kde každý uzol má najviac dvoch potomkov.
• Kompletný binárny strom: Na všetkých úrovniach, okrem možno poslednej, je strom úplne zaplnený. Uzly na poslednej úrovni sa zapĺňajú sprava doľava. To umožňuje efektívne uloženie hromady ako poľa.
• Vlastnosti hromady:
  • Max-hromada: Hodnota každého uzla je väčšia alebo rovná hodnotám jeho detí. Najväčší prvok je vždy na koreňovom vrchole.
  • Min-hromada: Hodnota každého uzla je menšia alebo rovná hodnotám jeho detí. Najmenší prvok je vždy na koreňovom vrchole.

Hlavné operácie s hromadou:

• Vkladanie prvku: Pridanie nového prvku a zachovanie vlastnosti hromady.
• Odstraňovanie prvku: Odstránenie koreňového prvku (najväčšieho alebo najmenšieho v závislosti od typu hromady) a zachovanie vlastnosti hromady.
• Vytvorenie hromady: Vytvorenie hromady z poľa prvkov.

Použitie hromady:

• Zoradenie: Heapsort algoritmus.
• Fronty s prioritou: Efektívna implementácia frontov, kde sa prvky spracúvajú podľa priority.
• Vyhľadávacie algoritmy: Napríklad hľadanie k-tého najväčšieho prvku.
• Grafové algoritmy: Napríklad Dijkstrov algoritmus.

Zobrazenie hromady ako poľa:

Keďže hromada je úplný binárny strom, môže sa efektívne uložiť do poľa bez použitia ukazovateľov.

• Ak sa uzol nachádza na indexe i, jeho ľavý potomok je na indexe 2*i + 1.
• Jeho pravý potomok je na indexe 2*i + 2.
• Jeho rodič je na indexe (i - 1) / 2.

# Príklad zobrazenia min-hromady ako poľa
heap_array = [10, 15, 20, 17, 25, 30]

# Koreň: heap_array[0] = 10
# Ľavý potomok koreňa: heap_array[2*0 + 1] = heap_array[1] = 15
# Pravý potomok koreňa: heap_array[2*0 + 2] = heap_array[2] = 20
# Rodič prvku na indexe 3 (17): heap_array[(3-1)//2] = heap_array[1] = 15