Wie funktioniert Heapsort?

Heapsort ist ein effizienter Vergleichssortieralgorithmus, der auf einem binären Heap-Datenstruktur basiert. Hier ist eine grundlegende Erklärung, wie Heapsort funktioniert:

1. **Heap-Bildung**: Zuerst wird das unsortierte Array in einen Max-Heap umgewandelt. Ein Max-Heap ist eine binäre Baumstruktur, bei der der Wert jedes Knotens größer oder gleich den Werten seiner Kinder ist.

2. **Sortieren**: Nachdem der Max-Heap erstellt wurde, wird das größte Element (die Wurzel des Heaps) mit dem letzten Element des Arrays getauscht. Das letzte Element wird dann aus dem Heap entfernt, und der Heap wird neu strukturiert, um die Max-Heap-Eigenschaft wiederherzustellen. Dieser Prozess wird wiederholt, bis alle Elemente sortiert sind.

Hier ist ein Beispiel in Pseudocode:

```
function heapsort(array):
buildMaxHeap(array)
for i from length(array) - 1 downto 1:
swap(array[0], array[i])
heapify(array, 0, i)

function buildMaxHeap(array):
for i from floor(length(array) / 2) downto 0:
heapify(array, i, length(array))

function heapify(array, i, heapSize):
left = 2 * i + 1
right = 2 * i + 2
largest = i

if left < heapSize and array[left] > array[largest]:
largest = left

if right < heapSize and array[right] > array[largest]:
largest = right

if largest != i:
swap(array[i], array[largest])
heapify(array, largest, heapSize)
```

**Vorteile von Heapsort**:
- Zeitkomplexität: O(n log n) im besten, durchschnittlichen und schlechtesten Fall.
- Platzkomplexität: O(1) zusätzlicher Speicherplatz, da es ein in-place Sortieralgorithmus ist.

**Nachteile von Heapsort**:
- Nicht stabil: Die relative Reihenfolge von Elementen mit gleichem Schlüsselwert kann sich ändern.
- Kann langsamer sein als andere O(n log n) Algorithmen wie Quicksort in der Praxis, da die Konstante in der Zeitkomplexität größer ist.

Weitere Informationen findest du auf [Wikipedia](https://de.wikipedia.org/wiki/Heapsort).