Algorithmen4Lerneinheiten21minStand30.05.2026

Heap & Heapsort.

Fachliche Qualität

Noch nicht klassifiziertNoch nicht geprüft.

Diese Lerneinheit wurde für typische Bachelor-Klausuren konzipiert. So prüfen wir · Fehler entdeckt? Melde ihn uns oder markiere die fragliche Stelle direkt im Text oben.

Klausur-ÜbersichtKomplette Übersicht: alle Tabs als linearer Text zum Lernen

Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).

Teil 1·Erklärung

Erklärung

Zur KategorieAlgorithmen.Mehr Themen entdeckenZum Themen-Hub.

Heap & Heapsort, Algorithmen · UniProMax

Du brauchst die Top-10-Werte aus 1 Million Datensätzen? Stell sie in einen Heap. Ein Heap ist die Standard-Datenstruktur für Priority Queues — und Heapsort ist der einzige $O(n \log n)$ -Sortier-Algorithmus mit $O(1)$ -Zusatzspeicher (in-place). Klausur-Pflicht in 14/17 WInf-Algo-Klausuren.

Heap: Ein vollständig binärer Baum, in dem jeder Eltern-Knoten kleiner (Min-Heap) oder größer (Max-Heap) ist als seine Kinder. Das Wurzel-Element ist also IMMER das Minimum oder Maximum.

Ein binärer Baum heißt vollständig, wenn:

Alle Ebenen außer der letzten voll gefüllt
Letzte Ebene von links nach rechts gefüllt

Wegen dieser Struktur lässt sich der Heap als Array speichern, ohne explizite Zeiger.

Bei Knoten an Index $i$ (0-basiert):

Linkes Kind: Index $2i + 1$
Rechtes Kind: Index $2i + 2$
Eltern: Index $\lfloor (i - 1) / 2 \rfloor$

Index:  0    1    2    3    4    5    6
Array: [10,  9,   8,   5,   6,   3,   2]

Als Baum:

       10
      /  \
     9    8
    / \   / \
   5   6 3   2

Das ist ein Max-Heap (Eltern ≥ Kinder).

Insert: $O(\log n)$

Element ans Ende des Arrays
Up-Heapify (auch "sift-up", "bubble-up"): tausche mit Eltern, solange Heap-Eigenschaft verletzt

insert(11):    [10, 9, 8, 5, 6, 3, 2, 11]
nach up-heap:  [11, 9, 10, 5, 6, 3, 2, 8] (tausche 11 mit 8, dann mit 10)

Wait — bei Max-Heap soll Wurzel max sein. Mit 11 muss es nach oben blubbern.

Tatsächlich: [10, 9, 8, 5, 6, 3, 2, 11] → 11 hat Eltern Index 3 = 5 → 5 < 11, tausche → [10, 9, 8, 11, 6, 3, 2, 5] → 11 hat Eltern Index 1 = 9 → 9 < 11, tausche → [10, 11, 8, 9, 6, 3, 2, 5] → 11 hat Eltern Index 0 = 10 → 10 < 11, tausche → [11, 10, 8, 9, 6, 3, 2, 5].

Extract-Max (für Max-Heap): $O(\log n)$

Wurzel-Element (Max) auslesen
Letztes Element an die Wurzel kopieren
Array um 1 verkürzen
Down-Heapify (auch "sift-down"): tausche mit größerem Kind, solange Heap-Eigenschaft verletzt

Build-Heap aus unsortiertem Array: $O(n)$

Bottom-Up: Starte ab dem letzten Eltern-Knoten ( $n/2 - 1$ ), gehe rückwärts, jeweils Down-Heapify.

Naive Methode (n-mal Insert) wäre $O(n \log n)$ . Bottom-Up ist $O(n)$ wegen amortisierter Analyse.

Build-Max-Heap aus Eingabe-Array: $O(n)$
N-mal: Extrahiere Max → tausche an die letzte Position → verkürze Heap → Down-Heapify: $O(n \log n)$

Insgesamt: $O(n \log n)$ , in-place mit $O(1)$ Zusatzspeicher.

heapsort(arr):
    build_max_heap(arr)
    for i in range(len(arr) - 1, 0, -1):
        swap arr[0] and arr[i]   # max ans Ende
        heap_size -= 1
        down_heapify(arr, 0, heap_size)

	Best	Avg	Worst	Speicher	In-Place
Heapsort	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(1)$	ja
Quicksort	$O(n \log n)$	$O(n \log n)$	$O(n^2)$	$O(\log n)$	ja
Mergesort	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(n)$	nein

Heapsort = beste Worst-Case-Garantie + in-place. In Praxis trotzdem oft langsamer als Quicksort wegen Cache-Performance.

Standard-API:

insert(value, priority): $O(\log n)$
extractMin() (oder Max): $O(\log n)$
peekMin(): $O(1)$
decreaseKey(value, newPriority): $O(\log n)$

Anwendungen:

Dijkstra (Priority Queue für nächsten Knoten)
Huffman-Codierung (zwei kleinste Knoten verschmelzen)
Task-Scheduling (Priorität nach Frist)
Top-K-Auswahl

Identische Datenstruktur, nur die Heap-Eigenschaft ist invertiert:

Min-Heap: Eltern ≤ Kinder → Wurzel = Minimum
Max-Heap: Eltern ≥ Kinder → Wurzel = Maximum

Heapsort nutzt typischerweise Max-Heap (für aufsteigende Sortierung). Priority Queues meist Min-Heap.

1. Heap = vollständig binärer Baum + Heap-Eigenschaft.

2. Array-Repräsentation: linke Kind = 2i+1, rechte Kind = 2i+2, Eltern = (i-1)/2.

3. Insert + Extract: $O(\log n)$ . Build-Heap aus Array: $O(n)$ (nicht $O(n \log n)$ ).

4. Heapsort: $O(n \log n)$ in jedem Fall, in-place mit $O(1)$ Zusatzspeicher.

5. Up-Heapify nach Insert, Down-Heapify nach Extract.

1. Heap ist KEIN BST. Heap-Eigenschaft betrifft nur Eltern-Kind, NICHT Geschwister oder linke/rechte Seiten. 5 kann links UND rechts vom Wurzel-7 stehen.

2. Index-Formeln verwechseln. 0-basiert vs. 1-basiert. Bei 0-basiert: 2i+1 und 2i+2. Bei 1-basiert: 2i und 2i+1.

3. Build-Heap mit n-mal Insert. Zwar korrekt, aber $O(n \log n)$ statt $O(n)$ . Bottom-Up Down-Heapify ist optimal.

4. Heapsort als stabil annehmen. Heapsort ist NICHT stabil — gleiche Schlüssel können ihre Reihenfolge ändern. Mergesort wäre stabil.

5. Min-Heap mit Max-Heap verwechseln. Bei Priority Queues meist Min-Heap (höhere Priorität = kleinere Zahl). Bei Heapsort meist Max-Heap. Lesen vor Schreiben!

Beobachte einen Heap als Baum + Array parallel. Du kannst:

Werte einfügen (Up-Heapify als Schritt-Folge)
Maximum extrahieren (Down-Heapify)
Ein neues Array aus Beispiel-Werten bauen

Sieh, wie sich die Heap-Eigenschaft Schritt für Schritt herstellt.

Lade Visualisierung...

Klausur-Tipp: Bei Heap-Aufgaben IMMER Baum + Array parallel zeichnen. Die Array-Indizes über jedes Element schreiben. So siehst du sofort, ob Eltern-Kind-Formeln passen.

Anmelden, um den Fortschritt zu speichern.

Nächster Schritt

Wenn du fertig bist: jetzt üben.

Aktives Abrufen festigt Wissen schneller als nochmal lesen.

Du brauchst die Top-10-Werte aus 1 Million Datensätzen? Stell sie in einen Heap. Ein Heap ist die Standard-Datenstruktur für Priority Queues — und Heapsort ist der einzige O(n log n)-Sortier-Algorithmus mit O(1)-Zusatzspeicher (in-place). Klausur-Pflicht in 14/17 WInf-Algo-Klausuren.

Die Idee in einem Satz

Heap: Ein vollständig binärer Baum, in dem jeder Eltern-Knoten kleiner (Min-Heap) oder größer (Max-Heap) ist als seine Kinder. Das Wurzel-Element ist also IMMER das Minimum oder Maximum.

Vollständig binärer Baum

Ein binärer Baum heißt vollständig, wenn:

Alle Ebenen außer der letzten voll gefüllt
Letzte Ebene von links nach rechts gefüllt

Wegen dieser Struktur lässt sich der Heap als Array speichern, ohne explizite Zeiger.

Array-Repräsentation

Bei Knoten an Index i (0-basiert):

Linkes Kind: Index 2i + 1
Rechtes Kind: Index 2i + 2
Eltern: Index lfloor (i - 1) / 2 rfloor

Index:  0    1    2    3    4    5    6
Array: [10,  9,   8,   5,   6,   3,   2]

Als Baum:

       10
      /  \
     9    8
    / \   / \
   5   6 3   2

Das ist ein Max-Heap (Eltern ≥ Kinder).

Operationen

Insert: `O(log n)`

Element ans Ende des Arrays
Up-Heapify (auch "sift-up", "bubble-up"): tausche mit Eltern, solange Heap-Eigenschaft verletzt

insert(11):    [10, 9, 8, 5, 6, 3, 2, 11]
nach up-heap:  [11, 9, 10, 5, 6, 3, 2, 8] (tausche 11 mit 8, dann mit 10)

Wait — bei Max-Heap soll Wurzel max sein. Mit 11 muss es nach oben blubbern.

Extract-Max (für Max-Heap): `O(log n)`

Wurzel-Element (Max) auslesen
Letztes Element an die Wurzel kopieren
Array um 1 verkürzen
Down-Heapify (auch "sift-down"): tausche mit größerem Kind, solange Heap-Eigenschaft verletzt

Build-Heap aus unsortiertem Array: `O(n)`

Bottom-Up: Starte ab dem letzten Eltern-Knoten (n/2 - 1), gehe rückwärts, jeweils Down-Heapify.

Naive Methode (n-mal Insert) wäre O(n log n). Bottom-Up ist O(n) wegen amortisierter Analyse.

Heapsort: `O(n log n)`

Build-Max-Heap aus Eingabe-Array: O(n)
N-mal: Extrahiere Max → tausche an die letzte Position → verkürze Heap → Down-Heapify: O(n log n)

Insgesamt: O(n log n), in-place mit O(1) Zusatzspeicher.

heapsort(arr):
    build_max_heap(arr)
    for i in range(len(arr) - 1, 0, -1):
        swap arr[0] and arr[i]   # max ans Ende
        heap_size -= 1
        down_heapify(arr, 0, heap_size)

Heapsort vs. Quicksort vs. Mergesort

	Best	Avg	Worst	Speicher	In-Place
Heapsort	`O(n log n)`	`O(n log n)`	`O(n log n)`	`O(1)`	ja
Quicksort	`O(n log n)`	`O(n log n)`	`O(n²)`	`O(log n)`	ja
Mergesort

Heapsort = beste Worst-Case-Garantie + in-place. In Praxis trotzdem oft langsamer als Quicksort wegen Cache-Performance.

Priority Queue mit Heap

Standard-API:

insert(value, priority): O(log n)
extractMin() (oder Max): O(log n)
peekMin(): O(1)
decreaseKey(value, newPriority): O(log n)

Anwendungen:

Dijkstra (Priority Queue für nächsten Knoten)
Huffman-Codierung (zwei kleinste Knoten verschmelzen)
Task-Scheduling (Priorität nach Frist)
Top-K-Auswahl

Min-Heap vs. Max-Heap

Identische Datenstruktur, nur die Heap-Eigenschaft ist invertiert:

Min-Heap: Eltern ≤ Kinder → Wurzel = Minimum
Max-Heap: Eltern ≥ Kinder → Wurzel = Maximum

Heapsort nutzt typischerweise Max-Heap (für aufsteigende Sortierung). Priority Queues meist Min-Heap.

Klausur-Faustregeln

1. Heap = vollständig binärer Baum + Heap-Eigenschaft.

2. Array-Repräsentation: linke Kind = 2i+1, rechte Kind = 2i+2, Eltern = (i-1)/2.

3. Insert + Extract: O(log n). Build-Heap aus Array: O(n) (nicht O(n log n)).

4. Heapsort: O(n log n) in jedem Fall, in-place mit O(1) Zusatzspeicher.

5. Up-Heapify nach Insert, Down-Heapify nach Extract.

Häufige Stolpersteine

1. Heap ist KEIN BST. Heap-Eigenschaft betrifft nur Eltern-Kind, NICHT Geschwister oder linke/rechte Seiten. 5 kann links UND rechts vom Wurzel-7 stehen.

2. Index-Formeln verwechseln. 0-basiert vs. 1-basiert. Bei 0-basiert: 2i+1 und 2i+2. Bei 1-basiert: 2i und 2i+1.

3. Build-Heap mit n-mal Insert. Zwar korrekt, aber O(n log n) statt O(n). Bottom-Up Down-Heapify ist optimal.

4. Heapsort als stabil annehmen. Heapsort ist NICHT stabil — gleiche Schlüssel können ihre Reihenfolge ändern. Mergesort wäre stabil.

5. Min-Heap mit Max-Heap verwechseln. Bei Priority Queues meist Min-Heap (höhere Priorität = kleinere Zahl). Bei Heapsort meist Max-Heap. Lesen vor Schreiben!

Teil 3·Quiz / Klausurfragen

Praxis-Übung

Heap & Heapsort — Praxis-Übung

6 Aufgaben zu Heap-Operationen, Komplexität, Array-Indices.

Klausurfragen mit Lösungen (6)

F1.Was ist die Heap-Eigenschaft (Max-Heap)?

Antwort: Jeder Eltern-Knoten ist größer oder gleich seinen Kindern

Erklärung: Max-Heap: Eltern ≥ Kinder (überall). Wurzel ist Max. Bei Min-Heap umgekehrt. Heap-Eigenschaft ist eine LOKALE Bedingung (nur Eltern-Kind), keine globale Sortierung.

F2.Im Array [50, 30, 40, 10, 20, 35, 25] (0-basiert): an welchem Index steht das LINKE Kind des Knotens an Index 1?

Antwort: 3

Erklärung: Linkes Kind von Index i ist 2i+1. Hier: 2·1+1 = 3. Array[3] = 10. Das passt: Index 1 ist 30, dessen Kinder sind Index 3 (10) und Index 4 (20). Max-Heap-Eigenschaft 30 ≥ 10 und 30 ≥ 20 ✓.

Typ: Zahlen-Eingabe

F3.Heapsort hat im Worst-Case eine Laufzeit von O(n log n).

Antwort: Wahr

Erklärung: RICHTIG. Heapsort: O(n log n) im Best, Average, UND Worst Case. Im Gegensatz zu Quicksort (Worst O(n²)). Heapsort hat die beste Worst-Case-Garantie aller in-place O(n log n)-Sortierungen.

Typ: Wahr/Falsch

F4.Was ist die Komplexität von Build-Heap aus einem unsortierten Array von n Elementen?

Antwort: O(n)

Erklärung: O(n) mit Bottom-Up Down-Heapify. Naive Methode (n-mal Insert) wäre O(n log n). Bottom-Up nutzt aus dass Blätter-Heaps trivial sind und höhere Knoten weniger Heaps haben.

F5.Welche Aussagen über Heaps sind RICHTIG?

Richtige Antworten: Heap = vollständig binärer Baum + Heap-Eigenschaft; Insert + Extract-Max sind O(log n); Heap kann als Array ohne Pointer gespeichert werden; Heap wird oft für Priority Queues genutzt

Erklärung: Richtig: vollst.+Heap-Eig., O(log n) Ops, Array-Speicherung, Priority Queue. Falsch: Heapsort NICHT stabil; Heap ist KEINE komplette Sortierung — nur Wurzel ist garantiert Min/Max.

Typ: Multi-Select

F6.Ordne Operation der Komplexität zu:

Zuordnungen:

Insert (Up-Heapify) → O(log n)
Extract-Max (Down-Heapify) → O(log n)
Build-Heap aus Array → O(n)
Peek (Wurzel anschauen) → O(1)

Erklärung: Standard-Heap-Komplexitäten. Insert/Extract O(log n) durch Baumhöhe. Build-Heap O(n) durch amortisierte Analyse. Peek O(1) durch direkten Wurzel-Zugriff.

Typ: Zuordnung

Teil 4·Quiz / Klausurfragen

Klausur-Quiz

Klausurfragen mit Lösungen (6)

F1.Eltern-Index in 0-basiertem Heap bei Knoten an Index 11?

Antwort: 5

Erklärung: Eltern-Formel: ⌊(i-1)/2⌋ = ⌊10/2⌋ = 5. Test: Index 5 hat Kinder 11 und 12. Passt.

Typ: Zahlen-Eingabe

F2.Heapsort ist eine in-place Sortierung (O(1) Zusatzspeicher).

Antwort: Wahr

Erklärung: RICHTIG. Heapsort sortiert direkt im Eingabe-Array, kein zusätzliches Array nötig. Mergesort braucht O(n) extra. Quicksort O(log n) für Rekursion-Stack.

Typ: Wahr/Falsch

F3.Was passiert bei Extract-Max aus dem Max-Heap [50, 30, 40, 10, 20, 35, 25]?

Antwort: Array wird zu [40, 30, 35, 10, 20, 25]

Erklärung: Schritt 1: Max=50 extrahiert. Schritt 2: Letztes Element 25 an Wurzel → [25, 30, 40, 10, 20, 35]. Schritt 3: Down-Heapify: 25 vs Kinder 30, 40. Größeres Kind=40, tausche → [40, 30, 25, 10, 20, 35]. Schritt 4: 25 vs Kinder 35 (kein 2. Kind hier). 35 > 25, tausche → [40, 30, 35, 10, 20, 25]. Antwort 0.

F4.Warum ist Build-Heap O(n) und nicht O(n log n)?

Antwort: Weil amortisierte Analyse: höhere Knoten haben kleinere Höhe-Summe Σ(n/2^h · h) = O(n)

Erklärung: Amortisierte Analyse: Knoten auf Höhe h (von unten) brauchen O(h) Arbeit. Anzahl Knoten auf Höhe h ist ≤ n/2^h. Summe: Σ(h=0 bis log n) (n/2^h · h) = O(n). Naive n-mal Insert wäre O(n log n).

F5.Ein Heap ist ein {{1}} binärer Baum mit der Heap-{{2}}: Eltern ≥ Kinder (Max-Heap). Insert braucht {{3}}-Heapify, Extract-Max braucht {{4}}-Heapify. Build-Heap aus Array ist {{5}}.

Lösungen pro Lücke:

{{1}}: vollständiger / vollständig / vollst.
{{2}}: Eigenschaft
{{3}}: Up / up
{{4}}: Down / down
{{5}}: O(n)

Erklärung: Heap-Vokabular. Vollständig + Heap-Eigenschaft, Up-Heapify nach Insert, Down-Heapify nach Extract, Build-Heap linear.

Typ: Lückentext

F6.Sortiere: Heapsort eines Arrays.

Richtige Reihenfolge:

Build-Max-Heap aus dem Array (O(n))
Tausche Wurzel (Max) mit letztem Element
Heap-Größe um 1 verringern (max ist jetzt am Ende)
Down-Heapify neue Wurzel (O(log n))
Wiederhole bis Heap-Größe = 1

Erklärung: Standard-Heapsort-Workflow. Build-Heap → n-mal: Swap → Shrink → Down-Heapify. Resultat: aufsteigend sortiert. Insgesamt O(n log n).

Typ: Reihenfolge

Heap & Heapsort.

Erklärung

Heap & Heapsort.

Erklärung

Die Idee in einem Satz

Vollständig binärer Baum

Array-Repräsentation

Operationen

Insert: $O(\log n)$

Extract-Max (für Max-Heap): $O(\log n)$

Build-Heap aus unsortiertem Array: $O(n)$

Heapsort: $O(n \log n)$

Heapsort vs. Quicksort vs. Mergesort

Priority Queue mit Heap

Min-Heap vs. Max-Heap

Klausur-Faustregeln

Häufige Stolpersteine

Heap-Stepper

Wenn du fertig bist: jetzt üben.

Die Idee in einem Satz

Vollständig binärer Baum

Array-Repräsentation

Operationen

Insert: `O(log n)`

Extract-Max (für Max-Heap): `O(log n)`

Build-Heap aus unsortiertem Array: `O(n)`

Heapsort: `O(n log n)`

Heapsort vs. Quicksort vs. Mergesort

Priority Queue mit Heap

Min-Heap vs. Max-Heap

Klausur-Faustregeln

Häufige Stolpersteine

Interaktiv verstehen

Heap-Stepper

Praxis-Übung

Heap & Heapsort — Praxis-Übung

Klausur-Quiz

Erklärung

Erklärung

Die Idee in einem Satz

Vollständig binärer Baum

Array-Repräsentation

Operationen

Insert: O(log⁡n)O(\log n)O(logn)

Extract-Max (für Max-Heap): O(log⁡n)O(\log n)O(logn)

Build-Heap aus unsortiertem Array: O(n)O(n)O(n)

Heapsort: O(nlog⁡n)O(n \log n)O(nlogn)

Heapsort vs. Quicksort vs. Mergesort

Priority Queue mit Heap

Min-Heap vs. Max-Heap

Klausur-Faustregeln

Häufige Stolpersteine

Heap-Stepper

Wenn du fertig bist: jetzt üben.

Die Idee in einem Satz

Vollständig binärer Baum

Array-Repräsentation

Operationen

Insert: O(log n)

Extract-Max (für Max-Heap): O(log n)

Build-Heap aus unsortiertem Array: O(n)

Heapsort: O(n log n)

Heapsort vs. Quicksort vs. Mergesort

Priority Queue mit Heap

Min-Heap vs. Max-Heap

Klausur-Faustregeln

Häufige Stolpersteine

Interaktiv verstehen

Heap-Stepper

Praxis-Übung

Heap & Heapsort — Praxis-Übung

Klausur-Quiz

Insert: $O(\log n)$

Extract-Max (für Max-Heap): $O(\log n)$

Build-Heap aus unsortiertem Array: $O(n)$

Heapsort: $O(n \log n)$

Insert: `O(log n)`

Extract-Max (für Max-Heap): `O(log n)`

Build-Heap aus unsortiertem Array: `O(n)`

Heapsort: `O(n log n)`