Stog vs hrpa
Stog je uređena lista u kojoj se umetanje i brisanje stavki liste može vršiti samo na jednom kraju koji se zove vrh. Zbog ovog razloga, stog se smatra strukturom podataka Last in First Out (LIFO). Hrpa je posebna struktura podataka koja se zasniva na stablima i zadovoljava posebno svojstvo koje se naziva svojstvo hrpe. Također, hrpa je potpuno stablo, što znači da nema praznina između listova stabla, tj. u kompletnom stablu svaki nivo se popunjava prije dodavanja novog nivoa stablu i čvorovi na datom nivou se popunjavaju od slijeva na desno.
Šta je stack?
Kao što je ranije spomenuto, stek je struktura podataka u kojoj se elementi dodaju i uklanjaju samo sa jednog kraja koji se zove vrh. Stacks dozvoljavaju samo dvije osnovne operacije koje se nazivaju push i pop. Operacija guranja dodaje novi element na vrh steka. Operacija pop uklanja element sa vrha steka. Ako je stek već pun, kada se izvrši push operacija, to se smatra prelivanjem steka. Ako se operacija ispucavanja izvodi na već praznom steku, to se smatra podtokom steka. Zbog malog broja operacija koje se mogu izvesti na steku, on se smatra ograničenom strukturom podataka. Dodatno, prema načinu na koji su definirane push i pop operacije, jasno je da elementi koji su zadnji dodani u stog prvi izlaze iz steka. Stoga se stog smatra LIFO strukturom podataka.
Šta je Heap?
Kao što je ranije spomenuto, hrpa je kompletno stablo koje zadovoljava svojstvo hrpe. Svojstvo hrpe navodi da, ako je y podređeni čvor x, onda bi vrijednost pohranjena u čvoru x trebala biti veća ili jednaka vrijednosti pohranjenoj u čvoru y (tj. vrijednost (x) ≥ vrijednost (y)). Ovo svojstvo implicira da će čvor s najvećom vrijednošću uvijek biti smješten u korijenu. Hrpa napravljena korištenjem ovog svojstva naziva se max-heap. Postoji još jedna varijacija svojstva hrpe koja govori suprotno od ovoga. (tj. vrijednost(x) ≤ vrijednost(y)). To implicira da bi čvor sa najmanjom vrijednošću uvijek bio smješten u korijenu, što se naziva min-heap. Postoji širok raspon operacija koje se izvode na hrpama kao što je pronalaženje minimuma (u min-hrpama) ili maksimuma (u maksimalnim hrpama), brisanje minimuma (u minimalnim hrpama) ili maksimuma (u maksimalnim hrpama), povećanje (u maksimalnim hrpama) -hrpe) ili tipka za smanjenje (u min-hrpama) itd.
Koja je razlika između steka i hrpe?
Glavna razlika između stekova i hrpe je u tome što je stog linearna struktura podataka, dok je hrpa nelinearna struktura podataka. Stack je uređena lista koja prati svojstvo LIFO, dok je hrpa kompletno stablo koje slijedi svojstvo hrpe. Nadalje, stack je ograničena struktura podataka koja podržava samo ograničen broj operacija kao što su push i pop, dok hrpa podržava širok spektar operacija kao što je pronalaženje i brisanje minimuma ili maksimuma, povećanje ili smanjenje ključa i spajanje.
