Heaps uitgelegd: binaire heap, sift-up, sift-down en priority queues

Een hoop (heap) is een datastructuur die maar één ding heel goed doet: steeds het kleinste (of grootste) element snel teruggeven. Daarmee is hij de motor achter elke prioriteitswachtrij (priority queue): de taakplanner van een besturingssysteem, het algoritme van Dijkstra (zie grafen) en "geef me de tien grootste waarden uit een miljoen".

Op het tentamen krijg je bijna altijd een trace-opgave: "voeg deze getallen in, hoe ziet de array eruit?" In sollicitaties is "gebruik een heap" het standaardantwoord op top-k-vragen. Op deze pagina werken we met een min-heap: het kleinste element staat bovenaan.

Een volledige boom in een array

Een binaire heap is een binaire boom met twee eigenschappen:

1. Vorm: de boom is volledig (complete). Alle niveaus zijn vol, behalve misschien het onderste, en dat wordt van links naar rechts gevuld.
2. Heap-eigenschap: elke ouder is kleiner dan of gelijk aan zijn kinderen. De wortel is dus altijd het minimum.

Let op: tussen broers of tussen verschillende takken geldt geen volgorde. Een heap is niet gesorteerd.

Omdat de boom volledig is, hoef je geen pointers op te slaan. Je zet de knopen niveau voor niveau in een array (0-geïndexeerd), en rekent de familie uit:

Voorbeeld: de array [1, 6, 2, 10, 13, 3, 5] is deze boom:

            1          index 0
         /     \
        6       2      index 1, 2
       / \     / \
     10   13  3   5    index 3, 4, 5, 6

Het kind op index 4 (13) heeft als ouder ⌊(4 - 1) / 2⌋ = 1, en dat is 6. Klopt.

Invoegen met sift-up

Invoegen gaat in twee stappen:

1. Zet het nieuwe element achteraan de array (de eerste vrije plek in de boom).
2. Laat het omhoog zakken (sift-up): zolang het kleiner is dan zijn ouder, wissel je ze om.

We voegen 3, 6, 2, 10, 13, 1, 5 in een lege min-heap in:

Elke wissel brengt het element één niveau omhoog. Een boom met n knopen heeft ongeveer log n niveaus, dus invoegen kost hoogstens O(log n).

Het minimum verwijderen met sift-down

Het minimum staat altijd op index 0. Het weghalen gaat zo:

1. Onthoud de wortel (dat is het antwoord).
2. Verplaats het laatste element naar de wortel en maak de array één korter.
3. Laat het omlaag zakken (sift-down): wissel met het kleinste kind zolang dat kind kleiner is. Zijn beide kinderen gelijk, kies dan het linker.

Vanaf [1, 6, 2, 10, 13, 3, 5] halen we twee keer het minimum weg:

Waarom met het kleinste kind wisselen? Wissel je met het grootste, dan wordt dat de ouder van het kleinere kind, en is de heap-eigenschap direct kapot.

Een gelijkspel ziet er zo uit: uit [1, 3, 3, 5] het minimum halen geeft eerst [5, 3, 3]. Beide kinderen zijn 3, dus wissel je met het linker: [3, 5, 3].

Code

class MinHeap:
    def __init__(self):
        self.a = []

    def voeg_toe(self, x):
        self.a.append(x)  # achteraan
        i = len(self.a) - 1
        while i > 0:  # sift-up
            ouder = (i - 1) // 2
            if self.a[i] >= self.a[ouder]:
                break
            self.a[i], self.a[ouder] = self.a[ouder], self.a[i]
            i = ouder

    def verwijder_min(self):
        minimum = self.a[0]
        laatste = self.a.pop()
        if self.a:
            self.a[0] = laatste  # laatste naar de wortel
            self._sift_down(0)
        return minimum

    def _sift_down(self, i):
        n = len(self.a)
        while True:
            links, rechts = 2 * i + 1, 2 * i + 2
            kleinste = i
            if links < n and self.a[links] < self.a[kleinste]:
                kleinste = links
            # strikt kleiner: bij gelijke kinderen blijft het linker gekozen
            if rechts < n and self.a[rechts] < self.a[kleinste]:
                kleinste = rechts
            if kleinste == i:
                return
            self.a[i], self.a[kleinste] = self.a[kleinste], self.a[i]
            i = kleinste


h = MinHeap()
for x in [3, 6, 2, 10, 13, 1, 5]:
    h.voeg_toe(x)
print(h.a)                # [1, 6, 2, 10, 13, 3, 5]
print(h.verwijder_min())  # 1
print(h.a)                # [2, 6, 3, 10, 13, 5]

import java.util.ArrayList;
import java.util.List;

static class MinHeap {
    final List<Integer> a = new ArrayList<>();

    void voegToe(int x) {
        a.add(x); // achteraan
        int i = a.size() - 1;
        while (i > 0) { // sift-up
            int ouder = (i - 1) / 2;
            if (a.get(i) >= a.get(ouder)) break;
            wissel(i, ouder);
            i = ouder;
        }
    }

    int verwijderMin() {
        int minimum = a.get(0);
        int laatste = a.remove(a.size() - 1);
        if (!a.isEmpty()) {
            a.set(0, laatste); // laatste naar de wortel
            siftDown(0);
        }
        return minimum;
    }

    private void siftDown(int i) {
        int n = a.size();
        while (true) {
            int links = 2 * i + 1, rechts = 2 * i + 2, kleinste = i;
            if (links < n && a.get(links) < a.get(kleinste)) kleinste = links;
            // strikt kleiner: bij gelijke kinderen blijft het linker gekozen
            if (rechts < n && a.get(rechts) < a.get(kleinste)) kleinste = rechts;
            if (kleinste == i) return;
            wissel(i, kleinste);
            i = kleinste;
        }
    }

    private void wissel(int i, int j) {
        int t = a.get(i);
        a.set(i, a.get(j));
        a.set(j, t);
    }
}

Heapify: een hele array in O(n)

Heb je al een array, dan kun je de elementen één voor één invoegen: n keer O(log n). Het kan sneller. Bij heapify (bottom-up heap construction) roep je sift-down aan op elke knoop die kinderen heeft, van achter naar voren: van index ⌊n/2⌋ - 1 terug naar 0.

Voor [9, 4, 7, 1, 8, 2, 6] (dus n = 7, start bij index 2):

Dit is O(n) en niet O(n log n), omdat de meeste knopen onderaan zitten en nauwelijks hoeven te zakken. De helft van de knopen zijn bladeren en zakken helemaal niet.

Heapsort

Heapsort gebruikt dezelfde bouwstenen: maak met heapify een heap en haal dan n keer de wortel weg. Met een min-heap komen de elementen er oplopend uit. De klassieke in-place variant gebruikt een max-heap en zet het weggehaalde maximum steeds achteraan in dezelfde array. Heapsort is altijd O(n log n), ook in het slechtste geval, en gebruikt O(1) extra geheugen, maar is niet stabiel. Meer over sorteeralgoritmen lees je bij sorteren.

Priority queues in Python en Java

In de praktijk gebruik je de ingebouwde heap.

import heapq

taken = []
heapq.heappush(taken, (2, "mail beantwoorden"))
heapq.heappush(taken, (1, "server herstarten"))
heapq.heappush(taken, (3, "koffie halen"))

while taken:
    prioriteit, taak = heapq.heappop(taken)  # kleinste prioriteit eerst
    print(prioriteit, taak)

# een bestaande lijst in O(n) omzetten
getallen = [9, 4, 7, 1, 8, 2, 6]
heapq.heapify(getallen)
print(getallen)  # [1, 4, 2, 9, 8, 7, 6]

import java.util.PriorityQueue;

static void prioriteiten() {
    // min-heap op prioriteit; een int[] is {prioriteit, taaknummer}
    PriorityQueue<int[]> taken = new PriorityQueue<>((x, y) -> Integer.compare(x[0], y[0]));
    taken.add(new int[] {2, 101});
    taken.add(new int[] {1, 102});
    taken.add(new int[] {3, 103});

    while (!taken.isEmpty()) {
        int[] t = taken.poll(); // kleinste prioriteit eerst
        System.out.println(t[0] + " " + t[1]);
    }
}

heapq werkt op een gewone lijst en is altijd een min-heap; voor een max-heap sla je -x op. Java's PriorityQueue is standaard ook een min-heap; met Comparator.reverseOrder() maak je er een max-heap van. Let op: heapq.heappop gebruikt intern een andere, snellere variant van sift-down. Het minimum klopt altijd, maar bij gelijke waarden kan de array er anders uitzien dan met de tentamenmethode ([1, 3, 3, 5] wordt bij heapq [3, 3, 5] in plaats van [3, 5, 3]). Traceer op het tentamen dus met de hand, niet met heapq.

Complexiteit

Veelgemaakte fouten op het tentamen

1. Met het verkeerde kind wisselen. Bij sift-down wissel je met het kleinste kind, niet met het linker of met het eerste kind dat kleiner is dan de ouder. Bij gelijke kinderen: het linker.
2. De wortel weghalen en alles opschuiven. Je verplaatst het laatste element naar de wortel; de rest van de array blijft staan.
3. Verkeerde indexformules. Bij een 0-geïndexeerde array zijn de kinderen 2i + 1 en 2i + 2. De formules 2i en 2i + 1 horen bij een 1-geïndexeerde heap.
4. Denken dat een heap gesorteerd is. [1, 6, 2, 10, 13, 3, 5] is een geldige heap, maar geen gesorteerde array.
5. Te vroeg stoppen met sift-up of sift-down. Een element kan meerdere niveaus moeten verhuizen; controleer na elke wissel opnieuw.

Samenvatting

• Een binaire min-heap is een volledige boom in een array waarin elke ouder ≤ zijn kinderen is.
• Ouder van i is ⌊(i - 1)/2⌋, kinderen zijn 2i + 1 en 2i + 2.
• Invoegen: achteraan toevoegen en sift-up. Minimum verwijderen: laatste naar de wortel en sift-down met het kleinste kind (bij gelijkspel links). Beide O(log n).
• Heapify bouwt een heap in O(n); heapsort sorteert in O(n log n).
• Gebruik in de praktijk heapq (Python) of PriorityQueue (Java) als prioriteitswachtrij.