Heap Sort
Baut einen Max-Heap und entnimmt der Reihe nach das größte Element.
- Vergleiche 0
- Tauschvorgänge 0
- sortierte Indizes 0
- Vergleich
- Tausch
- sortiert
Heap (Baumdarstellung)
Pseudocode
1 buildMaxHeap(a)
2 for i from n - 1 downto 1
3 swap a[0], a[i]
4 heapSize = heapSize - 1
5 siftDown(0)
6 siftDown(i)
7 l = 2i + 1; r = 2i + 2
8 largest = i
9 if l < heapSize and a[l] > a[largest]: largest = l
10 if r < heapSize and a[r] > a[largest]: largest = r
11 if largest != i
12 swap a[i], a[largest]
13 siftDown(largest)
Schritt-Log
Funktionsweise, Laufzeit und Speicher
Heap Sort betrachtet das Array als binären Baum: das Element an Index i hat seine Kinder an 2i+1 und 2i+2. Im ersten Schritt baut der Algorithmus aus dem Array einen Max-Heap auf, indem er für jeden inneren Knoten (von hinten beginnend) eine siftDown-Operation aufruft: das Element wird mit dem größeren seiner Kinder verglichen und gegebenenfalls nach unten getauscht, solange ein Kind größer ist. Nach dem Aufbau steht das Maximum des Arrays an der Wurzel (Index 0). Im zweiten Schritt tauscht der Algorithmus die Wurzel mit dem letzten Heap-Element, verkleinert den Heap um eins (das getauschte Element gilt jetzt als sortiert) und stellt mit einem siftDown an der Wurzel die Heap-Eigenschaft wieder her. Diese Phase wiederholt sich, bis der Heap leer ist. Sowohl der Heap-Aufbau (O(n)) als auch n-1 mal siftDown (jeweils O(log n)) ergeben zusammen die garantierte Gesamtlaufzeit O(n log n) in jedem Fall. Heap Sort arbeitet in-place (O(1) Zusatz-Speicher), ist aber nicht stabil.
Komplexität
- Best Case
O(n log n) - Average Case
O(n log n) - Worst Case
O(n log n) - Zusatz-Speicher
O(1)
Wann verwenden?
Erste Wahl, wenn der Worst-Case-Aufwand garantiert O(n log n) bleiben muss und kein zusätzlicher Speicher verfügbar ist, weil Heap Sort komplett in-place arbeitet. Eignet sich für Embedded- und Echtzeit-Systeme und springt in Introsort als Sicherheitsnetz ein, sobald Quick Sort zu tief rekursiert.