Heap und Heapsort

Code in:JavaC#PythonJavaScript

Kurz gesagt: Ein Heap ist ein fast vollständiger Binärbaum, der in einem Array steht und bei dem das größte (oder kleinste) Element immer an der Wurzel liegt; Heapsort sortiert an Ort und Stelle in O(n log n).

Problem

Die Top 10 aus einer Million

Der Shop hat eine Million Produkte und weiß, wie oft jedes verkauft wurde. Die Startseite braucht die Top 10 nach Verkäufen. Das wird bei jedem Öffnen der Seite berechnet.

Das Erste, was einem einfällt, ist, alle zu sortieren und die ersten 10 zu nehmen. Mergesort macht bei einer Million Produkten etwa 18,7 Millionen Vergleiche (siehe Mergesort). Du brauchst 10 Zeilen davon. Die anderen 999.990 Produkte werden umsonst sortiert.

Es gibt noch einen zweiten Schmerz. Quicksort sortiert an Ort und Stelle, fällt aber bei einem schlechten Pivot auf O(n²) (siehe Quicksort). Mergesort ist jedes Mal O(n log n), braucht aber ein zweites Array so groß wie das erste. Geht beides: an Ort und Stelle und jedes Mal O(n log n)?

Die Idee

Ein Heap: ein Baum in einem Array

Beide brauchen eine Struktur, die nur eins weiß: welches das größte ist. Es muss nicht alles sortiert sein.

Zeichne das Array als Baum. Index 0 ist die Spitze. Unter jedem Index i gibt es zwei Kinder:

• das linke Kind liegt bei 2i + 1;
• das rechte Kind liegt bei 2i + 2;
• der Elternknoten von Index i liegt bei (i - 1) / 2, mit Ganzzahldivision.

Es gibt keine Zeiger. Der Baum ist nur eine Art, das Array zu betrachten.

Das Array ist ein Heap (genauer ein Max-Heap), wenn jeder Elternknoten mindestens so groß ist wie seine Kinder. Dann liegt das größte immer bei Index 0. Das ist die einzige Ordnung, die es gibt: Geschwister können untereinander in beliebiger Reihenfolge stehen.

Sieh es dir an

Die Kinder und der Elternknoten per Index

Ein Heap aus sieben Verkaufszahlen. Das Programm geht die Elternknoten durch, gibt ihre Kinder aus und findet dann den Elternknoten von Index 4:

int[] heap = {58, 40, 25, 31, 12, 3, 7};
for (int i = 0; 2 * i + 2 < heap.length; i++) {
    int left = 2 * i + 1, right = 2 * i + 2;
    System.out.println(heap[i] + " -> " + heap[left] + " " + heap[right]);
}
int child = 4;
int parent = (child - 1) / 2;
System.out.println("der Elternknoten von " + heap[child] + " (Index " + child + ") ist " + heap[parent] + " (Index " + parent + ")");

Ausgabe

58 -> 40 25
40 -> 31 12
25 -> 3 7
der Elternknoten von 12 (Index 4) ist 40 (Index 1)

58 steht über 40 und 25, 40 über 31 und 12, 25 über 3 und 7. Jeder Elternknoten ist größer als seine Kinder, und 58 ist das größte.

(child - 1) / 2 ist eine Division ganzer Zahlen: 3 / 2 ist 1, der Rest fällt weg.

Sieh es dir an

Einsinken: wie aus einem Array ein Heap wird

Wie wird ein Array in beliebiger Reihenfolge zu einem Heap? Mit einer Operation: dem Einsinken (Sift Down). Das Element bei Index i wird mit seinen zwei Kindern verglichen. Ist eines davon größer, tauscht es den Platz mit dem größeren, und das Element sinkt weiter. Es hört auf, wenn es mindestens so groß ist wie seine Kinder oder wenn es keine Kinder gibt.

Der Aufbau lässt das Einsinken für jeden Elternknoten laufen, vom letzten bis zur Spitze. Die Blätter (die unterste Reihe) haben keine Kinder: Jedes von ihnen ist für sich ein Heap. Wenn du also zu einem Elternknoten kommst, sind die zwei Teilbäume unter ihm schon Heaps, und er muss nur noch an seinen Platz sinken.

static void siftDown(int[] a, int i, int n) {
    while (true) {
        int big = i;
        int left = 2 * i + 1, right = 2 * i + 2;
        if (left < n && a[left] > a[big]) big = left;
        if (right < n && a[right] > a[big]) big = right;
        if (big == i) return;
        swap(a, i, big);
        i = big;
    }
}

Heapsort ist der Aufbau plus eine weitere Schleife. Das Maximum liegt bei Index 0: Es tauscht mit dem letzten Element und ist jetzt an seinem endgültigen Platz. Der Heap schrumpft um eins, und die neue Spitze sinkt ein. Das geschieht n - 1 Mal:

static void buildHeap(int[] a) {
    for (int i = a.length / 2 - 1; i >= 0; i--) {
        siftDown(a, i, a.length);
    }
}

static void heapSort(int[] a) {
    buildHeap(a);
    for (int end = a.length - 1; end > 0; end--) {
        swap(a, 0, end);
        siftDown(a, 0, end);
    }
}

int[] sales = {12, 40, 7, 31, 58, 3, 25};
buildHeap(sales);
System.out.println("Heap: " + Arrays.toString(sales));
heapSort(sales);
System.out.println("Sortiert: " + Arrays.toString(sales));

Ausgabe

Heap: [58, 40, 25, 31, 12, 3, 7]
Sortiert: [3, 7, 12, 25, 31, 40, 58]

static void swap(int[] a, int i, int j) {
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

static void siftDown(int[] a, int i, int n) {
    while (true) {
        int big = i;
        int left = 2 * i + 1, right = 2 * i + 2;
        if (left < n && a[left] > a[big]) big = left;
        if (right < n && a[right] > a[big]) big = right;
        if (big == i) return;
        swap(a, i, big);
        i = big;
    }
}

static void buildHeap(int[] a) {
    for (int i = a.length / 2 - 1; i >= 0; i--) {
        siftDown(a, i, a.length);
    }
}

static void heapSort(int[] a) {
    buildHeap(a);
    for (int end = a.length - 1; end > 0; end--) {
        swap(a, 0, end);
        siftDown(a, 0, end);
    }
}

Schritt für Schritt, in Worten

1. Sieben Verkaufszahlen in einem Array. Dasselbe Array ist ein Baum: Die Kinder von Index i liegen bei 2i + 1 und 2i + 2.
2. Der Aufbau beginnt beim letzten Elternknoten, Index 2. siftDown: 7 ist kleiner als ihr Kind 25, also tauschen sie.
3. Index 1: 40 gegen 31 und 58. Das größere Kind ist 58: Tausch.
4. Die Wurzel: 12 tauscht mit 58 und sinkt weiter. Eine Ebene tiefer ist 40 größer: noch ein Tausch.
5. Ein Heap: Jeder Elternknoten ist mindestens so groß wie seine Kinder. Das Maximum, 58, liegt bei Index 0.
6. Heapsort: Das Maximum tauscht mit dem letzten Element. 58 steht an seinem endgültigen Platz, und der Heap schrumpft auf sechs.
7. Die neue Spitze, 7, sinkt ein: Tausch mit 40, dann mit 31. Oben steht jetzt 40, das nächste Maximum. Das wiederholt sich n - 1 Mal.

Es gibt kein zweites Array: Die Tausche geschehen im Array selbst. Das ist Sortieren an Ort und Stelle.

Probier es aus

Sage die Ausgabe voraus

Der Aufbau lässt das Einsinken vom letzten Elternknoten bis zur Spitze laufen. Was steht danach im Array?

int[] sales = {5, 9, 2, 8};
buildHeap(sales);
System.out.println(Arrays.toString(sales));

Antwort

[9, 8, 2, 5]

[9, 5, 2, 8]

[2, 5, 8, 9]

Prüfen

Probier es aus

Ergänze

Das linke Kind von Index i ist:

int left = , right = 2 * i + 2;

Prüfen

Die Idee

Was es kostet

• Einsinken: auf jeder Ebene zwei Vergleiche und höchstens ein Tausch. Ein Baum aus n Elementen hat etwa log₂ n Ebenen, also ist das Einsinken O(log n).
• Aufbau: Es sieht nach n Einsinkvorgängen mit je log n aus, ist aber O(n). Die Hälfte der Elemente sind Blätter und sinken gar nicht, ein Viertel geht höchstens eine Ebene tiefer, ein Achtel zwei … Die Summe liegt unter 2n.
• Heapsort: der Aufbau plus n - 1 Einsinkvorgänge von der Spitze: in jedem Fall O(n log n). Es gibt keine schlechte Eingabe, wie einen schlechten Pivot beim Quicksort.

Lass ihn gegen Mergesort laufen. Beide zählen ihre Vergleiche:

• Heap Sort O(n log n)
• Sortieren (Merge Sort) O(n log n)

Algorithmus	n = 10	n = 1.000	n = 100.000
Heap Sort	38	16.807	3.019.656
Sortieren (Merge Sort)	21	8.709	1.536.371

Der Code läuft in deinem Browser, in JavaScript. Die Zahl der Operationen ist in jeder Sprache gleich, weil der Algorithmus derselbe ist. Die Zeit hängt von der Maschine ab und dient nur zum Vergleich. „≈“ ist eine Schätzung anhand der Kurve: Ein so großes n führen wir nicht aus, damit die Seite nicht einfriert.

static void swap(int[] a, int i, int j) {
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

static void siftDown(int[] a, int i, int n) {
    while (true) {
        int big = i;
        int left = 2 * i + 1, right = 2 * i + 2;
        if (left < n && a[left] > a[big]) big = left;
        if (right < n && a[right] > a[big]) big = right;
        if (big == i) return;
        swap(a, i, big);
        i = big;
    }
}

static void buildHeap(int[] a) {
    for (int i = a.length / 2 - 1; i >= 0; i--) {
        siftDown(a, i, a.length);
    }
}

static void heapSort(int[] a) {
    buildHeap(a);
    for (int end = a.length - 1; end > 0; end--) {
        swap(a, 0, end);
        siftDown(a, 0, end);
    }
}

Die zwei Kurven wachsen gleich, aber Heapsort macht etwa doppelt so viele Vergleiche: bei 100.000 Verkaufszahlen 3.019.656 gegen 1.536.371. Jedes Einsinken von der Spitze geht fast bis nach unten, weil dort ein kleines Element hingesetzt wurde.

Es gibt noch etwas, das die Zählung nicht zeigt: den Speicher. Von Index i springt das Einsinken zu 2i + 1. In einem großen Array ist das weit weg, und der Prozessor wartet jedes Mal, bis das nächste Stück Speicher ankommt. Mergesort und Quicksort lesen der Reihe nach, und genau dann ist der Prozessor schnell. In der Praxis ist Heapsort also langsamer, obwohl er jedes Mal O(n log n) verspricht.

Genauer, für Neugierige

Warum ist das eingebaute sort nicht Heapsort? Wegen des eben Gesagten. Heapsort ist die Rückfalloption: In C# ist Array.Sort Introsort, der mit Quicksort beginnt und auf Heapsort umschaltet, wenn die Partitionierung zu tief wird. So behält er O(n log n), ohne jedes Mal den Preis von Heapsort zu zahlen. Heapsort ist auch nicht stabil: Zwei Produkte mit gleichen Verkaufszahlen können ihre Reihenfolge tauschen. Was das heißt, steht in der Lektion zur Stabilität.

Warum der Aufbau O(n) ist: In der Höhe h über dem Boden gibt es etwa n / 2ʰ⁺¹ Elemente, und jedes sinkt höchstens h Ebenen. Die Summe n · (1/4 + 2/8 + 3/16 + …) ist n · 1 = n.

Probier es aus

Finde den Fehler

Jemand hat Heapsort geschrieben, aber das sortierte Ergebnis kommt durcheinander heraus:

static void heapSort(int[] a) {
    buildHeap(a);
    for (int end = a.length - 1; end > 0; end--) {
        swap(a, 0, end);
        siftDown(a, 0, a.length);
    }
}

int[] sales = {12, 40, 7, 31, 58, 3, 25};
heapSort(sales);
System.out.println(Arrays.toString(sales));

Ausgabe

[58, 31, 40, 25, 12, 7, 3]

In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

1static void heapSort(int[] a) {2 buildHeap(a);3 for (int end = a.length - 1; end > 0; end--) {4 swap(a, 0, end);5 siftDown(a, 0, a.length);6 }7}

Prüfen

Sieh es dir an

Die Top 10, ohne alles zu sortieren

Zurück zur Startseite. Dreh die Idee um: Halte einen Min-Heap mit 10 Elementen, mit dem kleinsten davon an der Spitze. Das ist der „Zehnte“: die Latte, die ein Produkt überspringen muss, um hineinzukommen.

• Solange es weniger als 10 sind, kommt jedes Produkt hinein.
• Danach wird jedes neue nur mit der Spitze verglichen. Ist es größer, nimmt es den Platz der Spitze ein und sinkt. Wenn nicht, scheidet es nach einem Vergleich aus.

In Java ist PriorityQueue genau so ein Min-Heap: peek() liefert die Spitze, poll() nimmt sie heraus, add() fügt hinzu und steigt auf.

record Product(int id, int sold) {}

PriorityQueue<Product> best = new PriorityQueue<>(Comparator.comparingInt(Product::sold));
for (int id = 1; id <= 1_000_000; id++) {
    Product p = new Product(id, (int) (id * 48271L % 1_000_003));
    if (best.size() < 10) {
        best.add(p);
    } else if (p.sold() > best.peek().sold()) {
        best.poll();
        best.add(p);
    }
}
List<Product> top = new ArrayList<>(best);
top.sort(Comparator.comparingInt(Product::sold).reversed());
for (Product p : top) {
    System.out.println("Produkt " + p.id() + ": " + p.sold() + " verkauft");
}

Ausgabe

Produkt 188706: 1000002 verkauft
Produkt 377412: 1000001 verkauft
Produkt 566118: 1000000 verkauft
Produkt 754824: 999999 verkauft
Produkt 943530: 999998 verkauft
Produkt 132233: 999997 verkauft
Produkt 320939: 999996 verkauft
Produkt 509645: 999995 verkauft
Produkt 698351: 999994 verkauft
Produkt 887057: 999993 verkauft

Lass es gegen das Sortieren von allem bis zu einer Million laufen:

• Die Top 10 mit einem Heap O(n)
• Sortieren (Merge Sort) O(n log n)

Algorithmus	n = 10	n = 1.000	n = 100.000	n = 1.000.000
Die Top 10 mit einem Heap	15	1.177	100.410	1.000.467
Sortieren (Merge Sort)	21	8.709	1.536.371	18.674.993

Der Code läuft in deinem Browser, in JavaScript. Die Zahl der Operationen ist in jeder Sprache gleich, weil der Algorithmus derselbe ist. Die Zeit hängt von der Maschine ab und dient nur zum Vergleich. „≈“ ist eine Schätzung anhand der Kurve: Ein so großes n führen wir nicht aus, damit die Seite nicht einfriert.

Bei einer Million Produkten macht der Heap 1.000.467 Vergleiche und Mergesort 18.674.993. Die Arbeit ist O(n · log 10): Der Heap wird nie größer als 10, also gibt es fast genau einen Vergleich pro Produkt.

Genauer, für Neugierige

Ein Heap, aus dem du „das Wichtigste“ herausnimmst und dem du neue hinzufügst, ist eine Prioritätswarteschlange. Sie ist ein eigenes Thema im Modul „Datenstrukturen“: Dort geht es um das Aufsteigen, und darum, warum Aufgaben in einem Scheduler, Ereignisse in einer Simulation und Dijkstra alle darauf aufbauen.

PriorityQueue in Java ist ein Min-Heap nach natürlicher Ordnung. Für einen Max-Heap übergibst du Comparator.reverseOrder().

Wie es in den anderen Sprachen ist: Java hat PriorityQueue, C# PriorityQueue<TElement, TPriority>, Python heapq, und JavaScript hat keinen eingebauten Heap.

Übung

Die Top drei

Löse die Aufgabe in deinem Editor.

Die Top drei nach Verkäufen. Die Verkaufszahlen von zwölf Produkten sind 12, 40, 7, 31, 58, 3, 25, 44, 19, 36, 50, 8. Finde die drei größten mit einem Min-Heap, der nie mehr als drei Elemente hat, und gib sie ab dem größten aus.

Ausgabe

Die ersten drei: [58, 50, 44]

Weitere Aufgaben

• Ein Min-Heap von Hand. Schreibe siftDown so um, dass ein Elternknoten höchstens so groß ist wie seine Kinder. Sortiere damit die Verkaufszahlen in umgekehrter Reihenfolge.
• Die Vergleiche zählen. Füge dem Einsinken einen Zähler hinzu und lass Heapsort mit 7, 1000 und 100.000 Verkaufszahlen laufen. Wächst es wie n log n?
• Die untersten 10. Welche 10 Produkte verkaufen sich am schlechtesten? Was für einen Heap brauchst du jetzt?

Test

Teste dich

1. Ein Heap steht in einem Array. Die Spitze liegt bei Index 0. Wo liegen die Kinder von Index 3?

Bei 7 und 8Bei 6 und 7Bei 4 und 5

2. Was garantiert ein Max-Heap?

Jeder Elternknoten ist mindestens so groß wie seine Kinder, also liegt das Maximum bei Index 0Das linke Kind ist kleiner als das rechteDas Array ist sortiert

3. Du brauchst die Top 10 nach Verkäufen aus einer Million Produkten. Was macht die wenigste Arbeit?

Einen Min-Heap mit 10 Elementen halten und jedes neue mit seiner Spitze vergleichenZehnmal das Maximum in der ganzen Liste suchenAlle sortieren und die ersten 10 nehmen

4. Heapsort ist jedes Mal O(n log n) und braucht keinen zusätzlichen Speicher. Warum ist die eingebaute Sortierung nicht Heapsort?

Weil er nur mit ganzen Zahlen funktioniertWeil er im schlechtesten Fall O(n²) istEr macht etwa doppelt so viele Vergleiche wie Mergesort und springt im Speicher herum, während der Prozessor gern der Reihe nach liest

Prüfen

Lektion von vorn beginnen

Verwandte Lektionen

• Baut auf: Big-O: wie die Arbeit wächst · Bester, durchschnittlicher und schlechtester Fall · Mergesort und „Teile und herrsche“ · Quicksort und der schlechte Pivot
• Geht weiter in: Countingsort und Radixsort · Stabiles Sortieren und die eingebaute Sortierung · Prioritätswarteschlange · Dijkstra
• Aufgaben zum Thema: Sortieren