Heap Sort

Vergleichsbasiert

Baut einen Max-Heap auf und extrahiert wiederholt das Maximum — erzeugt so eine sortierte Sequenz direkt im Array.

Live-Visualisierung

Komplexität

Bester Fall	O(n log n)
Durchschnitt	O(n log n)
Schlechtester Fall	O(n log n)
Speicherkomplexität	O(1)
Stabiles Sortieren	Nein
In-Place	Ja

Legende

O(1): Konstant: Egal wie viele Elemente — der Aufwand bleibt gleich.
O(n): Linear: Doppelt so viele Elemente → doppelt so viel Aufwand.
O(n log n): Quasi-Linear: Wenig schlechter als linear — der Goldstandard für Sortieren.
O(n²): Quadratisch: 10× mehr Elemente → 100× mehr Aufwand. Langsam bei großen Listen.
Stabil: Stabile Sortierung: Gleiche Werte behalten ihre ursprüngliche Reihenfolge zueinander.
In-Place: In-Place: Sortiert direkt im vorhandenen Speicher, ohne eine Kopie der Liste anzulegen.
Vergleichsbasiert: Vergleichsbasiert: Der Algorithmus entscheidet nur durch „ist A kleiner als B?" — funktioniert mit beliebigen Werten.
Nicht-Vergleichsbasiert: Nicht-Vergleichsbasiert: Nutzt die Struktur der Zahlen selbst (z. B. Ziffern) — kann dadurch schneller als O(n log n) sein.

Implementierung

TypeScript-Implementierung — direkt kopierbereit.

function heapSort(arr: number[]): number[] {
  const n = arr.length;
  // Max-Heap aufbauen
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }
  // Elemente aus dem Heap extrahieren
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    heapify(arr, i, 0);
  }
  return arr;
}

function heapify(arr: number[], n: number, i: number): void {
  let largest = i;
  const left = 2 * i + 1;
  const right = 2 * i + 2;
  if (left < n && arr[left] > arr[largest]) largest = left;
  if (right < n && arr[right] > arr[largest]) largest = right;
  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, n, largest);
  }
}

Wie es funktioniert

Heap Sort nutzt die binäre Heap-Datenstruktur. Zuerst wird das Array mithilfe von Floyds Heapify-Verfahren in O(n) in einen Max-Heap umgewandelt (jedes Elternelement ist größer als seine Kinder). Dann wird wiederholt die Wurzel (das Maximum) mit dem letzten unsortierten Element getauscht, die Heap-Grenze um eins verkleinert und die Heap-Eigenschaft wiederhergestellt.

Vorteile: Garantiertes O(n log n) im schlechtesten Fall bei O(1) Hilfsspeicher — der einzige Vergleichssortierer mit beiden Eigenschaften gleichzeitig.

Nachteile: Schlechtes Cache-Verhalten (Sift-Down greift nicht-sequentiell auf den Speicher zu), und nicht stabil.

Wann verwenden: Wenn garantiertes O(n log n) ohne zusätzlichen Speicher benötigt wird. Wird auch in Introselect verwendet (der Algorithmus hinter C++'s nth_element).

Vergleiche Heap Sort direkt mit einem anderen Algorithmus

Code vergleichen →

Quick Sort Shell Sort