Šta je stek u kontekstu programiranja i koje vrste stekova postoje?

Heap je oblast u operativnom memoriji koja se koristi za dinamičku raspodelu memorije tokom izvršavanja programa.

Glavne osobine:

• Memorija se eksplicitno dodeljuje i oslobađa od strane programera (ili sakupljača smeća).
• Ne postoji stroga sekvenca dodeljivanja/oslobađanja blokova memorije.
• Upravljanje memorijom je složenije nego na steku, može dovesti do fragmentacije i curenja memorije.

Vrste hrpa (u kontekstu struktura podataka):

• Binarni hrpa (Binary Heap): Drvo koje zadovoljava svojstvo hrpa. Za svaki čvor (osim korena), njegova vrednost je manja ili veća od vrednosti roditelja.
  • Min Heap: Vrednost roditelja je uvek manja ili jednaka vrednostima potomaka. Najmanji element je u korenu.
  • Max Heap: Vrednost roditelja je uvek veća ili jednaka vrednostima potomaka. Najveći element je u korenu.
• Binomijalni hrpa (Binomial Heap): Kolekcija binomijalnih stabala koja zadovoljavaju određena svojstva. Podržava efikasne operacije spajanja.
• Fibonacci hrpa (Fibonacci Heap): Struktura podataka koja se koristi u algoritmima kao što je Dijkstrin algoritam. Obezbeđuje efikasnije amortizovane vremenske složenosti za neke operacije u poređenju sa binarnom hrpom.
• Pairing Heap: Jednostavna struktura podataka sa dobrim amortizovanim vremenima.
• Levi hrpa (Leftist Heap): Struktura podataka koja olakšava efikasno spajanje. Vaša osobina je "rang" ili "nulta dužina puta", koja se koristi za brzo objedinjavanje.

Ove vrste hrpa se koriste u raznim algoritmima, kao što su sortiranje (Heap Sort), implementacija redova prioriteta, algoritmi za pronalaženje najkraćeg puta i dr. Izbor konkretne vrste hrpa zavisi od potrebnih operacija i njihove vremenske efikasnosti.