Skup proti kopici
Sklad je urejen seznam, v katerega je mogoče vstavljanje in brisanje elementov seznama izvesti samo na enem koncu, imenovanem vrh. Zaradi tega razloga se sklad šteje za podatkovno strukturo Zadnji v prvem ven (LIFO). Kopica je posebna podatkovna struktura, ki temelji na drevesih in izpolnjuje posebno lastnost, imenovano lastnost kopice. Kup je tudi popolno drevo, kar pomeni, da med listi drevesa ni vrzeli, tj. v celotnem drevesu je vsaka raven zapolnjena, preden se drevesu doda nova raven, vozlišča na dani ravni pa so zapolnjena iz od leve proti desni.
Kaj je Stack?
Kot smo že omenili, je sklad podatkovna struktura, v kateri se elementi dodajajo in odstranjujejo samo z enega konca, imenovanega vrh. Skladi dovoljujejo samo dve osnovni operaciji, imenovani push in pop. Operacija potiskanja doda nov element na vrh sklada. Operacija pop odstrani element z vrha sklada. Če je sklad že poln, ko se izvede operacija potiskanja, se to obravnava kot prelivanje sklada. Če se operacija izpiranja izvede na že praznem skladu, se to šteje za pretok sklada. Zaradi majhnega števila operacij, ki jih je mogoče izvesti na skladu, velja za omejeno podatkovno strukturo. Poleg tega je glede na način, kako sta definirani operaciji potiskanja in izpiranja, jasno, da elementi, ki so bili zadnji dodani v sklad, gredo iz sklada prvi. Zato se sklad obravnava kot podatkovna struktura LIFO.
Kaj je Heap?
Kot je bilo že omenjeno, je kopica popolno drevo, ki izpolnjuje lastnost kopice. Lastnost kopice 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. Kopica, zgrajena s to lastnostjo, se imenuje največja kopica. Obstaja še ena različica lastnosti kopice, ki navaja obratno od tega. (tj. vrednost(x) ≤ vrednost(y)). To pomeni, da bi bilo vozlišče z najmanjšo vrednostjo vedno postavljeno v koren, kar se imenuje najmanjša kopica. Obstaja širok razpon operacij, ki se izvajajo na kopicah, kot je iskanje minimuma (v min-kupih) ali maksimuma (v maks. kupih), brisanje minimuma (v min-kupih) ali maksimuma (v maks. kupih), povečanje (v maks. -heaps) ali tipka za padanje (v min-heaps) itd.
Kakšna je razlika med skladom in kopico?
Glavna razlika med skladi in kopicami je, da medtem ko je sklad linearna podatkovna struktura, je kopica nelinearna podatkovna struktura. Sklad je urejen seznam, ki sledi lastnosti LIFO, medtem ko je kopica popolno drevo, ki sledi lastnosti kopice. Poleg tega je sklad omejena podatkovna struktura, ki podpira samo omejeno število operacij, kot sta push in pop, medtem ko kopica podpira širok nabor operacij, kot je iskanje in brisanje minimuma ali maksimuma, povečanje ali zmanjšanje ključa in združevanje.
