Stack vs Heap
A verem egy rendezett lista, amelyben a listaelemek beszúrása és törlése csak az egyik végén, a tetején végezhető el. Emiatt a verem a Last in First out (LIFO) adatszerkezetnek minősül. A kupac egy speciális adatstruktúra, amely fákon alapul, és megfelel a kupac tulajdonságnak nevezett speciális tulajdonságnak. Ezenkívül a kupac egy teljes fa, ami azt jelenti, hogy a fa levelei között nincsenek hézagok, azaz egy teljes fában minden szint kitöltésre kerül, mielőtt új szinttel adna hozzá a fához, és az adott szinten lévő csomópontok kitöltése balról jobbra.
Mi az a Stack?
Amint korábban említettük, a verem egy olyan adatstruktúra, amelyben az elemeket csak az egyik végéről, a tetejéről adják hozzá és távolítják el. A veremek csak két alapvető műveletet tesznek lehetővé, amelyeket push-nak és pop-nak neveznek. A push művelet egy új elemet ad a verem tetejére. A pop művelet eltávolít egy elemet a verem tetejéről. Ha a verem már megtelt, akkor a push művelet végrehajtásakor verem túlcsordulásnak minősül. Ha egy pop műveletet hajtanak végre egy már üres veremen, az verem alulcsordulásnak minősül. A veremen végrehajtható műveletek kis száma miatt korlátozott adatszerkezetnek tekinthető. Ezen túlmenően, a push és pop műveletek meghatározásának módja szerint egyértelmű, hogy a verembe utoljára hozzáadott elemek először kerülnek ki a veremből. Ezért a verem LIFO adatszerkezetnek minősül.
Mi az a Heap?
Amint korábban említettük, a kupac egy teljes fa, amely kielégíti a kupac tulajdonságot. A kupac tulajdonság kimondja, hogy ha y x gyermekcsomópontja, akkor az x csomópontban tárolt értéknek nagyobbnak vagy egyenlőnek kell lennie, mint az y csomópontban tárolt érték (azaz érték(x) ≥ érték(y)). Ez a tulajdonság azt jelenti, hogy a legnagyobb értékű csomópont mindig a gyökérben lesz. Az ezzel a tulajdonsággal megszerkesztett kupacot max-halomnak nevezzük. A kupac tulajdonságnak van egy másik változata is, amely ennek az ellenkezőjét állítja. (azaz érték(x) ≤ érték(y)). Ez azt jelenti, hogy a legkisebb értékű csomópont mindig a gyökérbe kerül, ezt nevezzük min-halomnak. A kupacokon számos műveletet hajtanak végre, mint például a minimum (min-halomban) vagy maximum (max-halomban) keresése, minimum (min-halomban) vagy maximum törlése (max-halomban), növelése (max-halomban) -halom) vagy csökkenő (min-halomban) gomb stb.
Mi a különbség a Stack és a Heap között?
A veremek és a kupacok közötti fő különbség az, hogy míg a verem egy lineáris adatstruktúra, addig a kupac egy nem lineáris adatstruktúra. A verem egy rendezett lista, amely a LIFO tulajdonságot követi, míg a kupac egy teljes fa, amely a kupac tulajdonságot követi. Ezenkívül a verem egy korlátozott adatstruktúra, amely csak korlátozott számú műveletet támogat, mint a push és pop, míg a kupac támogatja a műveletek széles skáláját, például a minimum vagy maximum keresését és törlését, a kulcs növelését vagy csökkentését, valamint az összevonást.
