Wat is een stack in de context van programmeren en welke soorten stacks bestaan er?

Heap is een gebied in het werkgeheugen dat wordt gebruikt voor dynamisch geheugenbeheer tijdens de uitvoering van een programma.

Belangrijkste kenmerken:

• Geheugen wordt expliciet toegewezen en vrijgegeven door de programmeur (of de garbage collector).
• Er is geen strikte volgorde voor het toewijzen/vrijgeven van geheugenblokken.
• Geheugenbeheer is complexer dan op de stack, wat kan leiden tot fragmentatie en geheugenlekken.

Soorten heaps (in de context van datastructuren):

• Binaire heap (Binary Heap): Een boom die voldoet aan de heap-eigenschap. Voor elke knoop (behalve de wortel) is de waarde kleiner of groter dan die van de ouder.
  • Min Heap: De waarde van de ouder is altijd kleiner of gelijk aan die van de kinderen. Het kleinste element bevindt zich in de wortel.
  • Max Heap: De waarde van de ouder is altijd groter of gelijk aan die van de kinderen. Het grootste element bevindt zich in de wortel.
• Binomiale heap (Binomial Heap): Verzameling van binomiale bomen die aan bepaalde eigenschappen voldoen. Ondersteunt efficiënte fusie-operaties.
• Fibonacci-heap (Fibonacci Heap): Datastructuur gebruikt in algoritmen zoals Dijkstra. Biedt meer efficiënte geamortiseerde tijden voor bepaalde operaties in vergelijking met de binaire heap.
• Pairing Heap: Eenvoudige datastructuur met goede geamortiseerde tijden.
• Leftist Heap: Datastructuur die efficiënte fusie vergemakkelijkt. Een belangrijke eigenschap is de "rang" of "nul-lengte pad", die wordt gebruikt voor snelle samenvoeging.

Deze soorten heaps worden gebruikt in diverse algoritmen, zoals sortering (Heap Sort), implementatie van prioriteitswachtrijen, kortste pad algoritmen, enz. De keuze van een specifiek type heap hangt af van de vereiste operaties en hun tijdsefficiëntie.