BottomUp-Heapsort ist ein Sortieralgorithmus, der 1990 von Ingo Wegener vorgestellt wurde und im Durchschnitt besser als Quicksort arbeitet. Er ist ein verbesserte Variante des Heapsort. 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 Heapsort (normal) finden beim Absenken eines Elements zwei Vergleiche statt:

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

Da der zweite Vergleich innerhalb des Heaps oft unnötig ist, da das Element ja abegesenkt werden muss, wird der Heapsort-Algorithmus wie folgt verändert:

Zunächst wird der Pfad, in welchem das Wurzelelement versenkt werden soll, bestimmt. 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 K kopiert und vorher alle Knoten ab K (inkl.) bis zum Nachfolgeknoten der Wurzel auf diesem Pfad um eine Ebene nach oben verschoben.

Beispiel

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

Baumstruktur:

            9
       /         \
      23         24
    /   \       /  \
   20   18     14  17
  / \   / \   / \  / \
 13 15 11 10  5  7 3  2
                                                                  

Das Element 9 muss abgesenkt werden, da es kleiner als min. ein Nachfolgeknoten ist. Der Algorithmus durchläuft nun den Pfad 2 -> 17 -> 24 -> 9. Nun wird der Pfad vom Blattknoten (2) 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:

           24           -------|                      24
       /         \             |                 /         \  
      23         17            9                23         17
    /   \       /  \           |               /   \      /   \  
   20   18     14      <-------|              20   18    14    9
  / \   / \   / \  / \                       / \   / \   / \  / \
 13 15 11 10  5  7 3  2                     13 15 11 10 5  7  3  2