Razlika med Stackom in Heapom

Stack proti Heapu

Sklad je urejen seznam, v katerega je mogoče vstavljanje in brisanje elementov seznama opraviti samo na enem koncu, ki se imenuje vrh. Zaradi tega se sklad šteje za podatkovno strukturo Last in First out (LIFO). Heap je posebna podatkovna struktura, ki temelji na drevesih in izpolnjuje posebno lastnost, imenovano lastnost heap. Prav tako je kopica celotno drevo, kar pomeni, da ni nobenih vrzeli med listi drevesa, tj. V celotnem drevesu se vsaka raven zapolni, preden drevesu dodate novo raven in vozlišča na določeni ravni so zapolnjena z levo proti desni.

Kaj je Stack?

Kot smo že omenili, je skladanje podatkovna struktura, v katero so elementi dodani in odstranjeni le z enega konca, imenovanega vrh. Kola omogočata samo dve temeljni operaciji, imenovani push in pop. Potisna operacija doda nov element na vrh zložbe. Operacija pop odstrani element z vrha skladovnice. Če je sveženj že poln, se med potiskanjem šteje kot preliv. Če se pop operacija izvaja na že praznem nizu, se šteje za pretok v nizu. Zaradi majhnega števila operacij, ki bi jih bilo mogoče opraviti na sveženju, velja za omejeno strukturo podatkov. Poleg tega je glede na način definiranja push in pop operacij jasno, da elementi, ki so bili nazadnje dodani v sklad, gredo najprej iz sklada. Zato se sklad šteje za LIFO strukturo podatkov.

Kaj je kup?

Kot smo že omenili, je kopica popolno drevo, ki izpolnjuje lastnost gomile. Lastnost Heap navaja, da če je y podrejeno vozlišče x, mora biti vrednost, shranjena v vozlišču x, večja ali enaka vrednosti, shranjeni v vozlišču y (tj. Vrednost (x) ≥ vrednost (y)). Ta lastnost pomeni, da bi bilo vozlišče z največjo vrednostjo vedno postavljeno v koren. Kopa, zgrajena s to lastnostjo, se imenuje max-heap. Obstaja še ena različica lastnosti heap, ki navaja obratno to. (tj. vrednost (x) ≤ vrednost (y)). To pomeni, da bi bilo vozlišče z najmanjšo vrednostjo vedno postavljeno v koren, tako imenovano min-kup. Obstaja široka paleta operacij, ki se izvajajo na skupinah, kot so iskanje najnižjega (v min-heap) ali največjega (v max-heap), brisanja minimalnega (v min-heap) ali maksimalnega (v max-heap), povečanega (v max -heaps) ali padajoči (v min-heap) tipki itd.

Kakšna je razlika med Stackom in Heapom?

Glavna razlika med skladi in množicami je v tem, da je stack linearna podatkovna struktura, vendar je kup nelinearna podatkovna struktura. Stack je urejen seznam, ki sledi lastnosti LIFO, medtem ko je heap popolno drevo, ki sledi lastnosti heap. Poleg tega je skladanje omejena struktura podatkov, ki podpira le omejeno število operacij, kot je push in pop, medtem ko heap podpira širok razpon operacij, kot so iskanje in brisanje najmanjšega ali največjega, povečanje ali zmanjšanje ključa in združevanje.