Heap Sort
Die Idee ist es im Array die Heap Eigenschaft herzustellen wodurch man einen Heap erhält. In diesem Heap tauscht man so lange die Element, stellt die Heap Eigenschaft wieder her und wiederholt das ganze, bis alle Elemente sortiert wurden.
Python Implementierung
Laufzeit
Die Laufzeit ist immer (worst, average, best - case): .
Bessere Verfahren mit dem Schlüssel-Vergleich Prinzip gibt es nicht.
→ Beweis, Skript Seite 51