Wat is een stapel (in de context van datastructuren)?

Een heap is een gespecialiseerde boom die wordt gebruikt als datastructuur. De belangrijkste eigenschap van een heap is de partiële ordening: voor elke knoop geldt dat de waarde van de ouderknoop groter of gelijk is aan die van een van zijn kinderen (max-heap) of kleiner of gelijk (min-heap).

Belangrijke kenmerken:

• Binaire boom: Wordt meestal geïmplementeerd als een binaire boom, waarbij elke knoop maximaal twee nakomelingen heeft.
• Volledige binaire boom: Op alle niveaus, behalve mogelijk het laatste, is de boom volledig gevuld. De knopen op het laatste niveau worden van links naar rechts gevuld. Dit maakt het mogelijk om de heap efficiënt op te slaan als een array.
• Eigenschap van de heap:
  • Max-heap: De waarde van elke knoop is groter of gelijk aan die van zijn nakomelingen. Het grootste element bevindt zich altijd aan de top.
  • Min-heap: De waarde van elke knoop is kleiner of gelijk aan die van zijn nakomelingen. Het kleinste element bevindt zich altijd aan de top.

Belangrijkste operaties met de heap:

• Element invoegen: Een nieuw element toevoegen en de heap-eigenschap behouden.
• Element verwijderen: Het root-element verwijderen (maximaal of minimaal, afhankelijk van het type heap) en de heap-eigenschap behouden.
• Heap bouwen: Een heap bouwen uit een array van elementen.

Toepassingen van de heap:

• Sortering: Heapsort-algoritme.
• Prioriteitswachtrijen: Efficiënte implementatie van wachtrijen waarbij elementen in prioriteitsvolgorde worden verwerkt.
• Zoekalgoritmen: Bijvoorbeeld, het zoeken naar het k-de grootste element.
• Grafalgoritmen: Bijvoorbeeld, Dijkstra's algoritme.

Representatie van de heap in een array:

Omdat de heap een volledige binaire boom is, kan deze efficiënt worden opgeslagen in een array zonder pointers.

• Als een knoop zich op index i bevindt, bevindt zijn linker kind zich op index 2*i + 1.
• Zijn rechter kind bevindt zich op index 2*i + 2.
• Zijn ouder bevindt zich op index (i - 1) / 2.

# Voorbeeld van representatie van een min-heap als array
heap_array = [10, 15, 20, 17, 25, 30]

# Wortel: heap_array[0] = 10
# Linker kind van de wortel: heap_array[2*0 + 1] = heap_array[1] = 15
# Rechter kind van de wortel: heap_array[2*0 + 2] = heap_array[2] = 20
# Ouder van het element op index 3 (17): heap_array[(3-1)//2] = heap_array[1] = 15