Heaps en priority queues
Wat Is een Heap?
Een heap is een complete binaire boom waarbij elke ouder voldoet aan de heap-eigenschap - altijd kleiner (min-heap) of altijd groter (max-heap) dan zijn kinderen. "Compleet" betekent dat elk niveau vol is, behalve mogelijk het laatste dat van links naar rechts wordt gevuld.
1 Min-heap
/ \
3 5
/ \
7 4
Omdat de boom compleet is, slaan we hem op in een platte array - geen pointers nodig. Voor index i: linkerkind = 2i + 1, rechterkind = 2i + 2, ouder = (i - 1) // 2.
Min-Heap vs Max-Heap
| Eigenschap | Min-Heap | Max-Heap | |------------|----------|----------| | Wortel | Kleinste element | Grootste element | | Ouder ≤ Kinderen? | ✅ Ja | ❌ Nee (≥) | | Extract geeft | Minimum | Maximum |
Python's heapq is standaard een min-heap. Voor een max-heap negeer je waarden bij insert en negeer je opnieuw bij extract.
Insert en Extract - Stap voor Stap
Insert - voeg toe aan het einde, dan bubble up (wissel met ouder zolang kleiner):
import heapq
h = [1, 3, 5, 7]
heapq.heappush(h, 2) # h becomes [1, 2, 5, 7, 3]
Extract min - wissel wortel met laatste element, verwijder laatste, dan sift down (wissel met kleinste kind):
smallest = heapq.heappop(h) # returns 1
Beide operaties kosten O(log n) omdat de boomhoogte log n is.
Heapify - Een Heap Bouwen in O(n)
heapq.heapify(arr) zet een lijst om naar een heap in O(n), niet O(n log n). Het werkt bottom-up door elke niet-bladknoop omlaag te ziften. Dit is een van de meest verrassende complexiteitsresultaten in de informatica.
Discussion
Sign in to join the discussion