Stack vs Heap
Stack on järjestatud loend, milles loendi üksuste sisestamist ja kustutamist saab teha ainult ühes otsas, mida nimetatakse ülemiseks. Sel põhjusel käsitletakse pinu kui LIFO (Last in First out) andmestruktuuri. Kuhja on spetsiaalne andmestruktuur, mis põhineb puudel ja täidab spetsiaalset omadust, mida nimetatakse hunniku omaduseks. Samuti on hunnik terviklik puu, mis tähendab, et puu lehtede vahel ei ole lünki, st terviklikul puul täidetakse iga tase enne puule uue taseme lisamist ja antud taseme sõlmed täidetakse alates vasakult paremale.
Mis on Stack?
Nagu varem mainitud, on virn andmestruktuur, milles elemente lisatakse ja eemaldatakse ainult ühest otsast, mida nimetatakse ülemiseks. Virnad võimaldavad ainult kahte põhitoimingut, mida nimetatakse push ja pop. Tõukeoperatsioon lisab virna ülaossa uue elemendi. Popoperatsioon eemaldab elemendi virna ülaosast. Kui virn on juba täis, siis tõuketoimingu sooritamisel käsitletakse seda virna ülevooluna. Kui hüpikoperatsioon tehakse juba tühja virnaga, loetakse seda virna allavooluks. Kuna virnaga saab teha operatsioone, peetakse seda piiratud andmestruktuuriks. Lisaks on push- ja pop-operatsioonide defineerimisel selge, et virna viimasena lisatud elemendid väljuvad virnast esimesena. Seetõttu käsitletakse pinu LIFO andmestruktuurina.
Mis on Heap?
Nagu varem mainitud, on hunnik terviklik puu, mis rahuldab kuhja omadusi. Kuhja omadus ütleb, et kui y on x alamsõlm, siis sõlmes x salvestatud väärtus peaks olema suurem või võrdne sõlmes y salvestatud väärtusega (st väärtus(x) ≥ väärtus(y)). See omadus tähendab, et suurima väärtusega sõlm paigutatakse alati juure. Seda omadust kasutades konstrueeritud hunnikut nimetatakse max-hunnikuks. On veel üks kuhja omaduse variatsioon, mis väidab selle vastupidist. (st väärtus(x) ≤ väärtus(y)). See tähendab, et väikseima väärtusega sõlm paigutatakse alati juure, mida nimetatakse min-hunnikuks. Kuhjadega tehakse laias valikus toiminguid, nagu miinimumi (min-hunnikutes) või maksimumi (maksimaalsetes hunnikutes) leidmine, miinimumi (min-hunnikutes) või maksimumi (max-hunnikutes) kustutamine, suurendamine (max-hunnikutes) -kuhjad) või kahanev (min-hunnikutes) klahv jne
Mis vahe on Stackil ja Heapil?
Peamine erinevus virnade ja hunnikute vahel seisneb selles, et kui virn on lineaarne andmestruktuur, siis hunnik on mittelineaarne andmestruktuur. Virn on järjestatud loend, mis järgib LIFO atribuuti, samas kui hunnik on täielik puu, mis järgib kuhja omadust. Peale selle on virn piiratud andmestruktuur, mis toetab vaid piiratud arvu tõuke- ja hüppamisoperatsioone, samas kui kuhja toetab mitmesuguseid toiminguid, nagu miinimumi või maksimumi leidmine ja kustutamine, võtme suurendamine või vähendamine ning liitmine.
