Stack vs halda
Hromada je usporiadaný zoznam, do ktorého je možné vkladať a mazať položky zoznamu iba na jednom konci zvanom horná časť. Z tohto dôvodu sa zásobník považuje za dátovú štruktúru Last in First Out (LIFO). Heap je špeciálna dátová štruktúra, ktorá je založená na stromoch a spĺňa špeciálnu vlastnosť nazývanú heap property. Halda je tiež kompletný strom, čo znamená, že medzi listami stromu nie sú medzery, tj. V úplnom strome je vyplnená každá úroveň pred pridaním novej úrovne do stromu a uzly v danej úrovni sú vyplnené z zľava doprava.
Čo je to Stack?
Ako už bolo spomenuté skôr, zásobník je dátová štruktúra, v ktorej sa prvky pridávajú a odoberajú iba z jedného konca, ktorý sa nazýva horný. Stohy umožňujú iba dve základné operácie nazývané push a pop. Operácia stlačenia pridá do hornej časti stohu nový prvok. Popová operácia odstráni prvok z hornej časti stohu. Ak je zásobník už plný, pri uskutočňovaní operácie stlačenia sa to považuje za pretečenie zásobníka. Ak sa popová operácia vykoná s už prázdnym zásobníkom, považuje sa to za podtečenie zásobníka. Kvôli malému počtu operácií, ktoré je možné na zásobníku vykonať, sa to považuje za obmedzenú dátovú štruktúru. Ďalej je podľa spôsobu, akým sú definované operácie push a pop, zrejmé, že prvky, ktoré boli do zásobníka pridané ako posledné, najskôr vyjdú zo zásobníka. 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 je y podradený uzol x, potom hodnota uložená v uzle x by mala byť väčšia alebo rovnaká ako hodnota uložená v uzle y (tj hodnota (x) ≥ hodnota (y)). Táto vlastnosť znamená, že uzol s najväčšou hodnotou by bol vždy umiestnený v koreňovom adresári. Hromada konštruovaná pomocou tejto vlastnosti sa nazýva max-heap. Existuje ďalšia variácia vlastnosti haldy, ktorá udáva opačnú situáciu. (tj hodnota (x) ≤ hodnota (y)). To znamená, že uzol s najmenšou hodnotou by bol vždy umiestnený v koreňovom adresári, čo sa nazýva min halda. Na hromadách sa vykonáva široká škála operácií, ako napríklad nájdenie minima (v minimálnych hromadách) alebo maxima (v maximálnych hromadách), vymazania minima (v minimálnych hromadách) alebo maxima (v maximálnych hromadách),zvýšenie (v maximálnych hromadách) alebo zníženie (v minimálnych hromadách) kľúča atď.
Aký je rozdiel medzi Stack a Heap?
Hlavný rozdiel medzi hromadami a hromadami je, že zatiaľ čo zásobník je lineárna dátová štruktúra, halda je nelineárna dátová štruktúra. Stack je zoradený zoznam, ktorý nasleduje po vlastnosti LIFO, zatiaľ čo halda je celý strom, ktorý nasleduje po vlastnosti haldy. Zásobník ďalej predstavuje obmedzenú dátovú štruktúru, ktorá podporuje iba obmedzený počet operácií ako 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.
