Rozdiel medzi zásobami a haldy

Stack vs Heap

Zásobník je usporiadaný zoznam, v ktorom je možné vkladať a mazať položky zoznamu iba na jednom konci nazývanom 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 štruktúra údajov, ktorá je založená na stromoch a spĺňa špeciálnu vlastnosť nazývanú vlastnosť haldy. Halda je tiež úplný 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é, zásobník je dátová štruktúra, v ktorej sú prvky pridané a odstránené iba z jedného konca nazývaného vrchol. Zásobníky povoľujú iba dve základné operácie nazývané push a pop. Operácia push pridá nový prvok na vrch stohu. Operácia pop odstráni prvok z vrchu stohu. Ak je zásobník už plný, po vykonaní operácie zatlačenia sa považuje za pretečenie zásobníka. Ak sa pop operácia vykonáva na už prázdnom zásobníku, považuje sa to za podtok zásobníka. Z dôvodu malého počtu operácií, ktoré by sa mohli vykonávať na zásobníku, sa považuje za obmedzenú štruktúru údajov. Ď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é, idú zo zásobníka ako prvé. Zásobník sa preto považuje za dátovú štruktúru LIFO.

Čo je Heap?

Ako už bolo spomenuté, halda je kompletný strom, ktorý spĺňa vlastnosti haldy. Vlastnosť haldy uvádza, že ak y je podradený uzol x, potom by hodnota uložená v uzle x 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 najvyššou hodnotou by bol vždy umiestnený v koreňovom adresári. Halda vytvorená pomocou tejto vlastnosti sa nazýva max. Halda. Existuje iná variácia vlastnosti haldy, ktorá uvádza jej opak. (t. j. hodnota (x) ≤ hodnota (y)). To znamená, že uzol s najmenšou hodnotou by bol vždy umiestnený v koreňovom adresári, teda nazývaný minihroma. Na haldy sa vykonáva široká škála operácií, ako je zisťovanie minima (v min. Haldy) alebo maxima (v max. Haldy), odstránenie minima (v min. Haldy) alebo maxima (v max. Haldy), zvýšenie (v max. - haldy) alebo klesajúci kľúč (v min. haldy) atď.

Aký je rozdiel medzi Stack a Heap?

Hlavný rozdiel medzi zásobníkmi a haldy je v tom, že zatiaľ čo zásobník je lineárna dátová štruktúra, halda je nelineárna dátová štruktúra. Stack je usporiadaný zoznam, ktorý sleduje vlastnosť LIFO, zatiaľ čo halda je kompletný strom, ktorý nasleduje po vlastnosti haldy. Zásobník je okrem toho obmedzená dátová štruktúra, ktorá podporuje iba obmedzený počet operácií, ako je push a pop, zatiaľ čo halda podporuje celý rad operácií, ako napríklad nájdenie a vymazanie minima alebo maxima, zvýšenie alebo zníženie kľúča a zlúčenie..