Heapsort wurde Anfang der 60er Jahre von Williams und Floyd entwickelt. Der Algorithmus benötigt auch im \emph{worst-case} nur $2n\lg n$ Vergleiche. Im Laufe der letzten 30 Jahre gab es diverse Vorschläge, um den \emph{average-} und \emph{worst-case} auf $n\lg n +o(n\lg n)$ zu drücken.

Diese Arbeit soll -- aufbauend auf die zunächst formal eingeführte Datenstruktur \emph{Heap} -- einen Überblick über die verbreiteten Verfahren geben. Im Detail werden

\begin{itemize} \item das klassische Heapsort (Williams/Floyd), \item Bottom-Up-Heapsort (Carlsson/Wegener), \item Binary-Insertion-Heapsort (Carlsson), \item Optimal-Heapsort (Gu/Zhu), \item Bottom-Up-Heapsort mit Schrittweitenverdopplung (Diekert) \& \item Balanced-Heapsort (eigene Variante) \end{itemize}

vorgestellt. Diesen Varianten ist allen gemein, daß sie keinen zusätzlichen Speicherplatz benötigen. Weitere Verfahren (zum Teil mit zusätzlichem Speicherbedarf) werden kurz skizziert.

Die Algorithmen wurden implementiert und die praktischen Ergebnisse mit den theoretischen verglichen.