Overview
Heap Sort baut einen max-heap und legt in jedem Schritt das groesste Element ans Ende.
Analogy
Wie eine Priority Queue: zuerst kommt immer der groesste Wert.
Step-by-step
- Array per heapify in einen max-heap umwandeln.
- Wurzel mit letztem unsortierten Element tauschen.
- heap_size um 1 verkleinern.
- Von der Wurzel aus sift-down ausfuehren.
- Wiederholen bis heap_size = 1.
Visual
[heap | sorted tail] - der sortierte Bereich waechst rechts.
Common mistakes
- Kinderindizes fuer 0-basierte Arrays falsch berechnen.
- heap_size nach extraction nicht reduzieren.
- Nach swap versehentlich sift-up statt sift-down nutzen.
Practice questions
- Heapify [4,10,3,5,1] Schritt fuer Schritt.
- Erklaeren, warum Heap Sort nicht stabil ist.
- Min-heap Version fuer absteigende Sortierung bauen.