Razlika između Stack i Heap

Stack vs Heap

Stack je naručeni popis u koji se umetanje i brisanje stavki popisa može obaviti samo na jednom kraju koji se zove vrh. Iz tog razloga, snop se smatra strukturom podataka Last in First out (LIFO). Heap je posebna struktura podataka koja se temelji na stablima i ona zadovoljava posebno svojstvo koje se naziva svojstvo heap. Također, gomila je cjelovito stablo, što znači da nema praznina između lišća stabla, tj. Kod cijelog stabla svaka se razina popunjava prije dodavanja nove razine na stablo, a čvorovi se na određenoj razini popunjavaju sa s lijeva nadesno.

Što je Stack?

Kao što je spomenuto ranije, snop je struktura podataka u koju se dodaju elementi i uklanjaju samo s jednog kraja koji se zove vrh. Stepovi omogućuju samo dvije temeljne operacije zvane push i pop. Push operacija dodaje novi element na vrh snopa. Operacija pop uklanja element s vrha snopa. Ako je snop već popunjen, kada se izvede push operacija, smatra se preljevom snopa. Ako se pop operacija izvodi na već praznom snogu, smatra se podmlažanjem snopa. Zbog malog broja operacija koje bi se mogle izvesti na hrpi, smatra se ograničenom strukturom podataka. Uz to, prema načinu definiranja push i pop operacija, jasno je da elementi koji su posljednji dodani u snop prvo ispadaju iz snopa. Stoga se snop smatra LIFO strukturom podataka.

Što je Heap?

Kao što je spomenuto ranije, gomila je kompletno stablo koje zadovoljava svojstvo gomile. Svojstvo Heap navodi da je, ako je y podređeni čvor x, vrijednost pohranjena u čvoru x trebala biti veća ili jednaka vrijednosti pohranjenoj u čvoru y (tj. Vrijednost (x) ≥ vrijednost (y)). Ovo svojstvo podrazumijeva da bi se čvor s najvećom vrijednošću uvijek nalazio u korijenu. Korak izgrađen pomoću ovog svojstva naziva se max-heap. Postoji još jedna varijacija svojstva heap koja navodi obrnuto. (tj. vrijednost (x) ≤ vrijednost (y)). To podrazumijeva da bi se čvor s najmanjom vrijednošću uvijek nalazio u korijenu, takozvani min-heap. Postoji širok raspon operacija koje se izvode na hrpama, kao što su pronalaženje minimalnih (u min-heps) ili maksimalnih (u max-heap), brisanje minimalnih (u min-heap) i maksimala (u max-heps), povećanje (u max -heaps) ili smanjuje (u min-heps) tipki, itd.

Koja je razlika između Stack-a i Heap-a?

Glavna razlika između skupova i hrpa je ta što je dok je hrpa linearna struktura podataka, heap je nelinearna struktura podataka. Stack je naručeni popis koji prati svojstvo LIFO, dok je heap cjelovito stablo koje slijedi svojstvo heop-a. Nadalje, snop je ograničena struktura podataka koja podržava samo ograničeni broj operacija kao push and pop, dok heap podržava širok raspon operacija poput pronalaska i brisanja minimalnih ili maksimalnih, povećavanja ili smanjenja ključa i spajanja.