Bottom-Up-Heapsort
# Bottom-Up-Heapsort

BottomUp-Heapsort ist ein Sortieralgorithmus, der u. a. 1990 von Ingo Wegener vorgestellt wurde und im Durchschnitt besser als Quicksort arbeitet, falls man Vergleichsoperationen hinreichend stark gewichtet. Es ist eine Variante von Heapsort, die vor allem zur Sortierung sehr großer Datenmengen geeignet ist, wenn (im Vergleich zu den notwendigen Vertauschungsoperationen) ein relativ hoher Aufwand pro Vergleichsoperation erforderlich ist.

Diese Variante wurde allerdings bereits 1986 von Svante Carlsson analysiert, der letztlich eine weitere Variante fand, die sogar eine worst-case-Laufzeit von nur n log n + O(n log log n) Vergleichen hat. Entdeckt wurde dieser Bottom-Up-Heapsort bereits von Robert W Floyd (bei einer Überarbeitung des ursprünglichen Heapsorts von Williams), der aber das Laufzeitverhalten dieser Variante nicht beweisen konnte.

Er benötigt zum Sortieren einer Folge von n Schlüsseln im schlechtesten Fall nur 1,5 n log n + 2n Schlüsselvergleiche. Im Durchschnittsfall benötigt BottomUp-Heapsort nur n log n + O(n) Schlüsselvergleiche.

## Prinzip der Sortierung

Beim Sortieren mit normalem Heapsort finden beim Absenken eines Elements zwei Vergleiche pro Ebene statt:

* Welcher der beiden Nachfolgeknoten des abzusenkenden Elements ist größer?
* Ist der nun bestimmte Nachfolgeknoten größer als das abzusenkende Element?

Nachdem ein Binärbaum zur Hälfte aus Blättern besteht und zudem beim Sortieren ehemalige Blätter mit ohnehin schon eher niedrigen Werten abgesenkt werden, ist es wahrscheinlich, dass ein Element bis zur Blattebene oder in deren Nähe abgesenkt werden muss. Deshalb kann es lohnend sein, auf den zweiten Vergleich zu verzichten und auf Verdacht bis zur Blattebene abzusenken.

In einem zweiten Schritt wird dann rückwärts überprüft, wie weit das Element wieder angehoben werden muss. Im günstigsten Fall (sehr große Felder mit nur wenigen Dubletten) kann dabei fast die Hälfte der insgesamt nötigen Vergleiche bei mäßigem Zusatzaufwand eingespart werden.

Weniger geeignet ist BottomUp-Heapsort zur Sortierung kleinerer Felder mit einfacher numerischer Vergleichsoperation und dann, wenn im Feld sehr viele Elemente gleichwertig sind (dann stimmt die Annahme nicht, dass meist bis in die Nähe der Blattebene abgesenkt werden muss).

## Algorithmus

Konkret wird der Heapsort-Algorithmus, was das Absenken betrifft, wie folgt verändert:

Zunächst wird der Pfad, in welchem das Wurzelelement versenkt werden soll, bestimmt. Dies geschieht durch die Ermittlung des jeweils größten Kindes (Pfad maximaler Kinder). Danach wird dieser bestimmte Pfad von unten nach oben (vom Blatt in Richtung Wurzel) durchlaufen. Hierbei wird bei jedem besuchten Knoten verglichen, ob er größer als das abzusenkende Wurzelelement ist. Ist dem so, wird das Wurzelelement an die Position des zuletzt besuchten Knotens kopiert und vorher der restliche Pfad um eine Ebene nach oben verschoben.

Alternativ kann man auch die Verschiebung von vornherein auf Verdacht bis zur Blattebene durchführen und später – soweit notwendig – wieder rückgängig machen. Wo Kopien relativ günstig durchgeführt werden können (weil etwa nur ein Zeiger kopiert wird), kann das insgesamt vorteilhaft sein.

## Beispiel

Heap: [9, 23, 24, 20, 18, 14, 17, 13, 15, 11, 10, 5, 7, 3, 2]

Baumstruktur:

Das Element 9 muss abgesenkt werden, da es kleiner als mindestens ein Nachfolgeknoten ist. Es wird als erstes der Pfad der maximalen Kinder (ausgehend von der Wurzel) bestimmt. Es ergibt sich also 9 - 24 - 17 - 3. Der Algorithmus durchläuft diesen Pfad nun von unten nach oben, also 3 -> 17 -> 24 -> 9. Nun wird der Pfad vom Blattknoten (3) beginnend solange durchlaufen, bis sich ein Knoten findet, der größer als 9 ist. Der Durchlauf endet folglich bei 17. Nun werden alle Knoten ab 17 bis zum Nachfolgeknoten der Wurzel (= 17 -> 24) um eine Ebene nach oben und der Knoten 9 an die Position von 17 verschoben. Folglich ändern 17 und 24 als Nachfolgeknoten und 9 als Wurzelknoten ihren Platz.

Heap: [24, 23, 17, 20, 18, 14, 9, 13, 15, 11, 10, 5, 7, 3, 2]

Baumstruktur:

## Implementierung

Einfache Beispielsimplementierung in C99:

Zu Vergleichszwecken gibt die Funktion die Anzahl der durchgeführten Vergleiche zurück.

