Wat is een stapel?

Een heap is een speciale boomstructuur die voldoet aan de heap-eigenschap. Deze eigenschap stelt dat voor elke knoop, behalve de wortel, de waarde van de sleutel van die knoop in een bepaalde relatie moet staan tot de waarde van de sleutel van zijn ouder. Er zijn twee hoofdtypen heaps:

• Max-heap: De waarde van de sleutel van elke knoop is niet kleiner dan die van zijn kinderen. Het grootste element bevindt zich in de wortel.
• Min-heap: De waarde van de sleutel van elke knoop is niet groter dan die van zijn kinderen. Het kleinste element bevindt zich in de wortel.

De heap wordt meestal geïmplementeerd als een array, wat efficiënte toegang tot de elementen mogelijk maakt en operaties vergemakkelijkt. De relatie tussen ouders en kinderen in de array is als volgt:

• Voor een element met index i (beginnend bij 0), bevindt zijn linker kind zich op index 2i + 1.
• Zijn rechter kind bevindt zich op index 2i + 2.
• Zijn ouder bevindt zich op index floor((i - 1) / 2).

Belangrijkste operaties op de heap:

• Invoegen: Een nieuw element toevoegen. Uitvoertijd O(log n), waarbij n het aantal elementen is.
• Extract-Max / Extract-Min: Het verwijderen en teruggeven van het maximale (bij max-heap) of minimale (bij min-heap) element. Uitvoertijd O(log n).
• Heapify (Heap opbouwen): Het omzetten van een willekeurig array in een heap. Uitvoertijd O(n).

Heaps worden gebruikt in sorteeralgoritmen (bijvoorbeeld heapsort), in prioriteitswachtrijen en in algoritmen voor het zoeken van kortste paden (bijvoorbeeld Dijkstra's algoritme).