Heap Sort

Q: Wann sollte ich Heapsort verwenden?

Verwende Heapsort, wenn du einen garantierten `O(n log n)`-Worst-Case mit nur `O(1)` zusätzlichem Speicher brauchst. Es vermeidet das `O(n²)`-Risiko von Quicksort ohne den `O(n)`-Puffer von Mergesort, auf Kosten von Stabilität und Cache-Leistung.

Q: Was ist der Unterschied zwischen Heapsort und Quicksort?

Beide sortieren in-place, aber Quicksort hat einen `O(n²)`-Worst-Case, während Heapsort `O(n log n)` garantiert. In der Praxis ist Quicksort wegen besserer Cache-Lokalität und weniger Vertauschungen meist schneller, weshalb Heapsort vor allem dann bevorzugt wird, wenn die Worst-Case-Schranke garantiert sein muss.

Zuletzt aktualisiert 1. Juli 2026

Heapsort behandelt das Array als binären Heap. Zuerst baut es einen Max-Heap auf, sodass das größte Element an der Wurzel steht (Index 0). Dann tauscht es wiederholt die Wurzel mit dem letzten unsortierten Element - fixiert damit das Maximum an seinem Platz - und lässt die neue Wurzel absinken, um die Heap-Eigenschaft wiederherzustellen. Drücke oben auf Abspielen, um den Aufbau des Heaps und die Extraktionen zu sehen.

Heapsort garantiert wie Mergesort eine Laufzeit von O(n log n), sortiert aber in-place mit nur O(1) zusätzlichem Speicher. Es ist nicht stabil und neigt zu schlechterem Cache-Verhalten als Quicksort, weshalb es oft gewählt wird, wenn sowohl eine garantierte Schranke als auch konstanter Speicher wichtig sind.

Zeit- und Speicherkomplexität

Fall	Komplexität	Anmerkungen
Bester Fall	O(n log n)	Aufbau + n Extraktionen
Durchschnittsfall	O(n log n)	Zufällige Reihenfolge
Schlechtester Fall	O(n log n)	Garantiert
Speicher	O(1)	In-place
Stabil	Nein	Das Absinken ordnet gleiche Elemente um

Schritt für Schritt

Schritt	Was passiert
1	Aus dem Array einen Max-Heap aufbauen (vom letzten Elternknoten absinken lassen).
2	Die Wurzel (das Maximum) mit dem letzten Element des Heaps tauschen.
3	Den Heap um eins verkleinern - dieser letzte Platz ist nun sortiert.
4	Die neue Wurzel absinken lassen, um die Max-Heap-Eigenschaft wiederherzustellen.
5	Wiederholen, bis der Heap nur noch ein Element enthält.

Durchgerechnetes Beispiel

Sortieren von [3, 1, 6, 5, 2, 4]. Der Balken | markiert die Grenze zwischen dem schrumpfenden Heap und dem sortierten Ende:

Durchlauf	Array	Aktion
Heap aufbauen	`[6, 5, 4, 1, 2, 3]`	Vom letzten Elternknoten absinken lassen, um den Max-Heap aufzubauen; `6` steht nun an der Wurzel.
1	`[5, 3, 4, 1, 2 \| 6]`	Wurzel `6` mit dem letzten Platz tauschen, den Heap verkleinern und `3` absinken lassen.
2	`[4, 3, 2, 1 \| 5, 6]`	Wurzel `5` herausnehmen, dann `2` absinken lassen, sodass `4` an die Wurzel aufsteigt.
3	`[3, 1, 2 \| 4, 5, 6]`	Wurzel `4` herausnehmen, dann `1` absinken lassen, sodass `3` an die Wurzel aufsteigt.
4	`[2, 1 \| 3, 4, 5, 6]`	Wurzel `3` herausnehmen; `2` erfüllt die Heap-Eigenschaft bereits.
5	`[1 \| 2, 3, 4, 5, 6]`	Wurzel `2` herausnehmen; ein Element bleibt übrig, also ist das Array sortiert.

Wann man Heapsort einsetzt

Einsetzen, wenn	Vermeiden, wenn
Du einen garantierten `O(n log n)`-Worst-Case ohne Risiko von `O(n²)` brauchst.	Du eine stabile Sortierung brauchst, die die Reihenfolge gleicher Schlüssel bewahrt.
Der Speicher knapp ist - es sortiert in-place mit nur `O(1)` zusätzlichem Speicher.	Cache-Leistung zählt und die Daten in den Speicher passen - Quicksort ist meist schneller.
Du bereits einen Heap (z. B. eine Prioritätswarteschlange) über die Daten führst.	Du möglichst wenige Vergleiche willst - Mergesort und Quicksort machen in der Praxis oft weniger.
Nicht vertrauenswürdige Eingaben Quicksorts Worst-Case auslösen könnten und du nicht randomisieren kannst.	Die Daten fast sortiert sind - Insertionsort läuft darauf in nahezu linearer Zeit.

Heap Sort-Code

Eine saubere, lauffähige Heap Sort-Implementierung in Python, JavaScript, Java, C++, C. Wähle eine Sprache, kopiere den Code oder öffne ihn vorgeladen im Coddy-Playground.

Heap Sort-Code in PythonPython
1def heap_sort(a):2    n = len(a)3    # Build a max-heap, deepest parent first4    for i in range(n // 2 - 1, -1, -1):5        sift_down(a, i, n)6    # Repeatedly move the max to the end and shrink the heap7    for end in range(n - 1, 0, -1):8        a[0], a[end] = a[end], a[0]9        sift_down(a, 0, end)10    return a11
12
13def sift_down(a, i, size):14    while True:15        largest = i16        left, right = 2 * i + 1, 2 * i + 217        if left < size and a[left] > a[largest]:18            largest = left19        if right < size and a[right] > a[largest]:20            largest = right21        if largest == i:22            return23        a[i], a[largest] = a[largest], a[i]24        i = largest25
26
27nums = [12, 11, 13, 5, 6, 7]28print("Before:", nums)29heap_sort(nums)30print("After: ", nums)
Führe diesen Code im Python-Playground aus

Heap Sort-Code in JavaScriptJavaScript
1function heapSort(a) {2    const n = a.length;3    // Build a max-heap, then repeatedly move the max to the end4    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) siftDown(a, i, n);5    for (let end = n - 1; end > 0; end--) {6        [a[0], a[end]] = [a[end], a[0]];7        siftDown(a, 0, end);8    }9    return a;10}11
12function siftDown(a, i, size) {13    while (true) {14        const left = 2 * i + 1;15        const right = 2 * i + 2;16        let largest = i;17        if (left < size && a[left] > a[largest]) largest = left;18        if (right < size && a[right] > a[largest]) largest = right;19        if (largest === i) return;20        [a[i], a[largest]] = [a[largest], a[i]];21        i = largest;22    }23}24
25const data = [5, 2, 9, 1, 7, 3];26console.log("Before:", data);27console.log("Sorted:", heapSort([...data]));
Führe diesen Code im JavaScript-Playground aus

Heap Sort-Code in JavaJava
1import java.util.Arrays;2
3public class Main {4    static void heapSort(int[] arr) {5        int n = arr.length;6        // Build a max-heap, deepest parent first7        for (int i = n / 2 - 1; i >= 0; i--) siftDown(arr, i, n);8        // Repeatedly move the max to the end and shrink the heap9        for (int end = n - 1; end > 0; end--) {10            swap(arr, 0, end);11            siftDown(arr, 0, end);12        }13    }14
15    static void siftDown(int[] arr, int i, int size) {16        while (true) {17            int largest = i, l = 2 * i + 1, r = 2 * i + 2;18            if (l < size && arr[l] > arr[largest]) largest = l;19            if (r < size && arr[r] > arr[largest]) largest = r;20            if (largest == i) return;21            swap(arr, i, largest);22            i = largest;23        }24    }25
26    static void swap(int[] arr, int a, int b) {27        int tmp = arr[a];28        arr[a] = arr[b];29        arr[b] = tmp;30    }31
32    public static void main(String[] args) {33        int[] arr = {12, 11, 13, 5, 6, 7};34        System.out.println("Before: " + Arrays.toString(arr));35        heapSort(arr);36        System.out.println("After:  " + Arrays.toString(arr));37    }38}
Führe diesen Code im Java-Playground aus

Heap Sort-Code in C++C++
1#include <iostream>2#include <utility>3#include <vector>4
5void printVec(const std::vector<int>& a) {6    for (int x : a) std::cout << x << " ";7    std::cout << "\n";8}9
10void siftDown(std::vector<int>& a, int n, int i) {11    while (true) {12        int largest = i, l = 2 * i + 1, r = 2 * i + 2;13        if (l < n && a[l] > a[largest]) largest = l;14        if (r < n && a[r] > a[largest]) largest = r;15        if (largest == i) return;16        std::swap(a[i], a[largest]);17        i = largest;18    }19}20
21void heapSort(std::vector<int>& a) {22    int n = static_cast<int>(a.size());23    // Build a max-heap in place24    for (int i = n / 2 - 1; i >= 0; --i) siftDown(a, n, i);25    // Repeatedly move the max to the end and shrink the heap26    for (int end = n - 1; end > 0; --end) {27        std::swap(a[0], a[end]);28        siftDown(a, end, 0);29    }30}31
32int main() {33    std::vector<int> data = {12, 11, 13, 5, 6, 7};34    std::cout << "Before: ";35    printVec(data);36    heapSort(data);37    std::cout << "After:  ";38    printVec(data);39    return 0;40}
Führe diesen Code im C++-Playground aus

Heap Sort-Code in CC
1#include <stdio.h>2
3void printArr(const int a[], int n) {4    for (int i = 0; i < n; i++) printf("%d ", a[i]);5    printf("\n");6}7
8void siftDown(int a[], int n, int i) {9    while (1) {10        int largest = i, l = 2 * i + 1, r = 2 * i + 2;11        if (l < n && a[l] > a[largest]) largest = l;12        if (r < n && a[r] > a[largest]) largest = r;13        if (largest == i) return;14        int tmp = a[i];15        a[i] = a[largest];16        a[largest] = tmp;17        i = largest;18    }19}20
21void heapSort(int a[], int n) {22    // Build a max-heap in place23    for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, n, i);24    // Repeatedly move the max to the end and shrink the heap25    for (int end = n - 1; end > 0; end--) {26        int tmp = a[0];27        a[0] = a[end];28        a[end] = tmp;29        siftDown(a, end, 0);30    }31}32
33int main(void) {34    int data[] = {12, 11, 13, 5, 6, 7};35    int n = sizeof(data) / sizeof(data[0]);36    printf("Before: ");37    printArr(data, n);38    heapSort(data, n);39    printf("After:  ");40    printArr(data, n);41    return 0;42}
Führe diesen Code im C-Playground aus

Heapsort-FAQ

Wie hoch ist die Zeitkomplexität von Heapsort?

Heapsort ist im besten, im durchschnittlichen und im schlechtesten Fall O(n log n). Der Aufbau des Heaps ist O(n), und jede der n Extraktionen kostet O(log n). Es verwendet O(1) zusätzlichen Speicher.

Ist Heapsort stabil?

Nein. Die Absink-Operation kann gleiche Elemente aneinander vorbeischieben, daher bewahrt Heapsort nicht die relative Reihenfolge gleicher Schlüssel.

Wann sollte ich Heapsort verwenden?

Verwende Heapsort, wenn du einen garantierten O(n log n)-Worst-Case mit nur O(1) zusätzlichem Speicher brauchst. Es vermeidet das O(n²)-Risiko von Quicksort ohne den O(n)-Puffer von Mergesort, auf Kosten von Stabilität und Cache-Leistung.

Was ist der Unterschied zwischen Heapsort und Quicksort?

Beide sortieren in-place, aber Quicksort hat einen O(n²)-Worst-Case, während Heapsort O(n log n) garantiert. In der Praxis ist Quicksort wegen besserer Cache-Lokalität und weniger Vertauschungen meist schneller, weshalb Heapsort vor allem dann bevorzugt wird, wenn die Worst-Case-Schranke garantiert sein muss.

Wie hängt Heapsort mit einer Prioritätswarteschlange zusammen?

Ein binärer Heap ist die Standardimplementierung einer Prioritätswarteschlange, und Heapsort besteht im Wesentlichen darin, wiederholt das Maximum aus dieser Warteschlange zu entnehmen. Wenn du deine Daten bereits in einem Heap hältst, liefert dir das Herausnehmen der Elemente eins nach dem anderen die sortierte Reihenfolge gratis.

Braucht Heapsort einen Max-Heap oder einen Min-Heap?

Um in-place aufsteigend zu sortieren, verwende einen Max-Heap: Das größte Element wird bei jedem Durchlauf ans Ende getauscht, sodass das sortierte Ende von rechts wächst. Ein Min-Heap würde in-place absteigende Reihenfolge erzeugen, oder aufsteigende, wenn du in ein separates Array extrahierst.