Stack vs Heap
Zásobník je usporiadaný zoznam, do ktorého je možné vkladať a mazať položky zoznamu iba na jednom konci, ktorý sa nazýva horný. Z tohto dôvodu sa zásobník považuje za dátovú štruktúru Last in First Out (LIFO). Halda je špeciálna dátová štruktúra, ktorá je založená na stromoch a spĺňa špeciálnu vlastnosť nazývanú vlastnosť haldy. Hromada je tiež úplný strom, čo znamená, že medzi listami stromu nie sú žiadne medzery, t.j. v úplnom strome je každá úroveň vyplnená pred pridaním novej úrovne do stromu a uzly v danej úrovni sú vyplnené z zľava doprava.
Čo je zásobník?
Ako už bolo spomenuté, zásobník je dátová štruktúra, v ktorej sa prvky pridávajú a odstraňujú iba z jedného konca, ktorý sa nazýva vrchol. Zásobníky umožňujú iba dve základné operácie nazývané push a pop. Operácia push pridá nový prvok do hornej časti zásobníka. Operácia pop odstráni prvok z hornej časti zásobníka. Ak je zásobník už plný, pri vykonaní operácie push sa to považuje za pretečenie zásobníka. Ak sa operácia pop vykoná na už prázdnom zásobníku, považuje sa to za podtečenie zásobníka. Vzhľadom na malý počet operácií, ktoré je možné vykonať na zásobníku, sa považuje za obmedzenú dátovú štruktúru. Okrem toho, podľa spôsobu, akým sú definované operácie push a pop, je jasné, že prvky, ktoré boli do zásobníka pridané ako posledné, vychádzajú zo zásobníka ako prvé. Preto sa zásobník považuje za dátovú štruktúru LIFO.
Čo je halda?
Ako už bolo spomenuté, halda je úplný strom, ktorý spĺňa vlastnosť haldy. Vlastnosť haldy uvádza, že ak y je podriadený uzol x, potom hodnota uložená v uzle x by mala byť väčšia alebo rovná hodnote uloženej v uzle y (t. j. hodnota (x) ≥ hodnota (y)). Táto vlastnosť znamená, že uzol s najväčšou hodnotou by bol vždy umiestnený v koreňovom adresári. Halda vytvorená pomocou tejto vlastnosti sa nazýva maximálna halda. Existuje ďalšia variácia vlastnosti haldy, ktorá uvádza opak. (t. j. hodnota (x) ≤ hodnota (y)). To znamená, že uzol s najmenšou hodnotou by bol vždy umiestnený v koreni, teda nazývaný min-hromada. Existuje široká škála operácií vykonávaných s hromadami, ako je nájdenie minima (v minimálnych hromadách) alebo maxima (v maximálnych hromadách), vymazanie minima (v minimálnych hromadách) alebo maxima (v maximálnych hromadách), zvýšenie (v max. -heaps) alebo klesajúci (v min-hromadách) kľúč atď.
Aký je rozdiel medzi zásobníkom a haldou?
Hlavný rozdiel medzi zásobníkmi a haldami je v tom, že kým zásobník je lineárna dátová štruktúra, halda je nelineárna dátová štruktúra. Zásobník je usporiadaný zoznam, ktorý nasleduje po vlastnosti LIFO, zatiaľ čo halda je úplný strom, ktorý nasleduje po vlastnosti haldy. Okrem toho zásobník je obmedzená dátová štruktúra, ktorá podporuje iba obmedzený počet operácií, ako je push a pop, zatiaľ čo halda podporuje širokú škálu operácií, ako je nájdenie a odstránenie minima alebo maxima, zvýšenie alebo zníženie kľúča a zlúčenie.
