Stack vs Heap
Stog je poredani popis na kojem se umetanje i brisanje stavki popisa može izvršiti samo na jednom kraju koji se naziva gornji. Iz tog se razloga stog smatra strukturom podataka Posljednji u prvom (LIFO). Hrpa je posebna struktura podataka koja se temelji na stablima i zadovoljava posebno svojstvo koje se naziva svojstvo hrpe. Također, hrpa je cjelovito stablo, što znači da nema praznina između lišća stabla, tj. U cjelovitom stablu svaka se razina popunjava prije dodavanja nove razine stablu, a čvorovi na zadanoj razini popunjavaju se iz s lijeva nadesno.
Što je Stack?
Kao što je ranije spomenuto, stog je struktura podataka u kojoj se elementi dodaju i uklanjaju sa samo jednog kraja koji se naziva vrh. Snopovi omogućuju samo dvije temeljne operacije zvane push i pop. Operacija guranja dodaje novi element na vrh stoga. Skočna operacija uklanja element s vrha stoga. Ako je stog već pun, kada se izvodi push operacija, to se smatra preljevom stoga. Ako se pop operacija izvodi na već praznom snopu, smatra se podtokom steka. Zbog malog broja operacija koje bi se mogle izvesti na stogu, smatra se ograničenom strukturom podataka. Uz to, prema načinu na koji su definirane push i pop operacije, jasno je da elementi koji su dodani zadnji u stog prvi izlaze iz stoga. Stoga se stog smatra LIFO strukturom podataka.
Što je Heap?
Kao što je ranije spomenuto, hrpa je cjelovito stablo koje zadovoljava svojstvo hrpe. Svojstvo heap navodi da, ako je y podređeni čvor x, tada vrijednost pohranjena u čvor x treba biti veća ili jednaka vrijednosti pohranjenoj u čvoru y (tj. Vrijednost (x) ≥ vrijednost (y)). Ovo svojstvo podrazumijeva da bi čvor s najvećom vrijednošću uvijek bio smješten u korijenu. Hrpa konstruirana pomoću ovog svojstva naziva se max-heap. Postoji još jedna varijacija svojstva hrpe koja navodi obrnuto od ovoga. (tj. vrijednost (x) ≤ vrijednost (y)). To podrazumijeva da bi čvor s najmanjom vrijednošću uvijek bio smješten u korijenu, tako nazvan min-hrpa. Postoji širok spektar operacija koje se izvode na gomilama, poput pronalaženja minimuma (u min gomilama) ili maksimuma (u max gomilama), brisanja minimuma (u min gomilama) ili maksimuma (u max gomilama),tipka za povećanje (u maks. hrpama) ili u opadanju (u min. hrpama) itd.
Koja je razlika između stoga i hrpe?
Glavna razlika između stogova i hrpa je u tome što je dok je stog linearna struktura podataka, hrpa je nelinearna struktura podataka. Stog je poredani popis koji slijedi svojstvo LIFO, dok je hrpa cjelovito stablo koje slijedi svojstvo hrpe. Nadalje, stog je ograničena struktura podataka koja podržava samo ograničeni broj operacija kao što su push i pop, dok hrpa podržava širok raspon operacija poput pronalaženja i brisanja minimuma ili maksimuma, povećanja ili smanjenja ključa i spajanja.
