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).
Erklärung
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.
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.
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 | 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.
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!
Interaktiv verstehen
Heap-Stepper
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.
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
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.
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
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
