Heap Sort
Zuletzt aktualisiert
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 Python
Python
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)Heap Sort-Code in JavaScript
JavaScript
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]));Heap Sort-Code in Java
Java
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}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}Heap Sort-Code in C
C
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}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.
Verwandte Ressourcen
Mehr Visualisierungen
