Co je to zásobník v kontextu programování a jaké druhy zásobníků existují?

Hromádek (Heap) je oblast v operační paměti, která se používá pro dynamické přidělování paměti během běhu programu.

Hlavní vlastnosti:

• Paměť je explicitně přidělována a uvolňována programátorem (nebo garbage collectorem).
• Neexistuje přísný sled při přidělování/uvolňování bloků paměti.
• Správa paměti je složitější než na zásobníku, může vést k fragmentaci a únikům paměti.

Typy hald (v kontextu datových struktur):

• Binární halda (Binary Heap): Strom, který splňuje vlastnost haldy. Pro každý uzel (kromě kořene) je jeho hodnota menší nebo větší než hodnota rodiče.
  • Min halda: Hodnota rodiče je vždy menší nebo rovna hodnotám potomků. Nejmenší prvek je v kořeni.
  • Max halda: Hodnota rodiče je vždy větší nebo rovna hodnotám potomků. Největší prvek je v kořeni.
• Binomální halda (Binomial Heap): Kolekce binomálních stromů, které splňují určité vlastnosti. Podporuje efektivní operace slučování.
• Fibonacci halda (Fibonacci Heap): Datová struktura používaná v algoritmech jako Dijkstrův algoritmus. Zajišťuje efektivnější amortizované časy pro některé operace ve srovnání s binární haldou.
• Pairing Heap: Jednoduchá datová struktura s dobrými amortizovanými časy.
• Leftist Heap: Datová struktura usnadňující efektivní slučování. Důležitou vlastností je "ranga" nebo "délka nulové cesty", která se používá pro rychlé spojení.

Tyto typy hald se používají v různých algoritmech, například třídění (Heap Sort), implementaci prioritních front, algoritmech hledání nejkratší cesty atd. Výběr konkrétního typu haldy závisí na požadovaných operacích a jejich časové efektivitě.