Snop protiv gomile
Stop je uređeni popis u kojem se umetanje i brisanje stavki popisa može učiniti samo na jednom kraju koji se naziva vrh. Iz tog razloga, stog se smatra strukturom podataka Last in First Out (LIFO). Hrpa je posebna struktura podataka koja se temelji 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 potpunom stablu svaka se razina popunjava prije dodavanja nove razine stablu, a čvorovi na danoj razini popunjavaju se iz slijeva nadesno.
Što je Stack?
Kao što je ranije spomenuto, stog je struktura podataka u kojoj se elementi dodaju i uklanjaju samo s jednog kraja koji se naziva vrh. Stogovi dopuštaju samo dvije temeljne operacije koje se zovu push i pop. Operacija guranja dodaje novi element na vrh stoga. Operacija pop uklanja element s vrha stoga. Ako je stog već pun, kada se izvrši push operacija, to se smatra prekoračenjem stoga. Ako se operacija iskakanja izvodi na već praznom stogu, to se smatra nedostatkom stoga. Zbog malog broja operacija koje se mogu izvesti na stogu, on se smatra ograničenom strukturom podataka. Dodatno, prema načinu na koji su definirane operacije push i pop, jasno je da elementi koji su posljednji dodani na stog prvi izlaze iz stoga. Stoga se stog smatra LIFO strukturom podataka.
Što je Heap?
Kao što je ranije spomenuto, gomila je potpuno stablo koje zadovoljava svojstvo gomile. Svojstvo gomile navodi da, ako je y podređeni čvor od x, tada 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 bi čvor s najvećom vrijednošću uvijek bio smješten u korijenu. Hrpa konstruirana pomoću ovog svojstva naziva se max-hop. Postoji još jedna varijacija svojstva hrpe koja govori obrnuto od ovoga. (tj. vrijednost(x) ≤ vrijednost(y)). To implicira da bi čvor s najmanjom vrijednošću uvijek bio smješten u korijenu, što se naziva min-hop. Postoji širok raspon operacija koje se izvode na gomilama, kao što je pronalaženje minimuma (u min-hrpama) ili maksimuma (u maksimalnim hrpama), brisanje minimuma (u min-hrpama) ili maksimuma (u maksimalnim hrpama), povećanje (u maks. -heaps) ili tipka za smanjenje (u min-heaps), itd.
Koja je razlika između hrpe i gomile?
Glavna razlika između hrpe i hrpe je ta što je hrpa linearna struktura podataka, dok je hrpa nelinearna struktura podataka. Stog je uređena lista koja slijedi svojstvo LIFO, dok je hrpa potpuno stablo koje slijedi svojstvo hrpe. Nadalje, hrpa je ograničena struktura podataka koja podržava samo ograničen broj operacija kao što su push i pop, dok hrpa podržava širok raspon operacija kao što su pronalaženje i brisanje minimuma ili maksimuma, povećanje ili smanjenje ključa i spajanje.
