/ Algorithmen & Komplexität

Heap Sort Vergleiche

Anzahl Vergleiche beim Heap Sort im Worst Case: Vergleiche = 2 · n · log₂(n). Garantierte O(n log n)-Laufzeit ohne zusätzlichen Speicher.

01 · Eingabe

Heap Sort Vergleiche berechnen

Anzahl Vergleiche beim Heap Sort im Worst Case: Vergleiche = 2 · n · log₂(n). Garantierte O(n log n)-Laufzeit ohne zusätzlichen Speicher.

Vergleiche = 2 · n · log₂(n)

n Elementanzahl

Worum geht es?

Heap Sort baut aus der Eingabe einen binären Max-Heap und entnimmt wiederholt das Maximum. Pro Entnahme fallen bis zu log₂(n) Vergleiche im Sift-Down an — über alle n Schritte ergibt sich asymptotisch 2 · n · log₂(n) Vergleiche im Worst Case.

Vorteile: garantierte O(n log n)-Laufzeit, in-place (Θ(1) Zusatzspeicher), kein pathologischer Worst Case wie bei Quick Sort. Nachteil: nicht stabil und cache-unfreundlich, weil das Heap-Layout über das gesamte Array streut.

Die Formel

Formel Heap Sort

Vergleiche = 2 · n · log₂(n)

Die Variablen

Symbol	Bedeutung	Einheit	Erklärung
n	Elementanzahl	—	Anzahl zu sortierender Elemente.
Vergleiche	Vergleiche	—	Anzahl Vergleiche (Worst Case).

Minimal-Beispiel

n = 1024:

Rechnung Vergleiche

Vergleiche = 2 · 1024 · log₂(1024)
           = 2 · 1024 · 10
           = 20 480

Praxis-Beispiele

Beispiel 1 — Eine Million Elemente

Rechnung n = 10⁶

Vergleiche = 2 · 1 000 000 · 19,93
           ≈ 39 860 000

Beispiel 2 — Vergleich der O(n log n)-Sortierer

n = 10⁶:

Rechnung Vergleich

Merge:  1,00 · n · log₂(n)  ≈ 2,0 · 10⁷
Quick:  1,39 · n · log₂(n)  ≈ 2,8 · 10⁷
Heap:   2,00 · n · log₂(n)  ≈ 4,0 · 10⁷

Beispiel 3 — Einsatzfall in Introsort

Heap Sort wird in Introsort (z. B. C++ std::sort) als Fallback genutzt, wenn Quick Sort zu tief rekursiv wird:

Rechnung Hybrid

Wechsel auf Heap Sort, sobald
    Rekursionstiefe > 2 · log₂(n)

Damit ist der Worst Case auf O(n log n) garantiert.