2. Suchen und Sortieren

2.4 Heapsort

Heapsort

Der zweite effiziente Algorithmus, den wir kennenlernen, ist Heapsort. Der für diese Vorlesung vielleicht wichtigste Grund, warum wir ihn drannehmen ist, dass er eine schlaue Datenstruktur verwendet, die wir später im Kontekt von Graphenalgorithmen wieder brauchen werden: den Heap.

Heaps sind gut, weil sie zwei wichtige Operationen effizient unterstützen:

Ein neues Element in einen Heap einfügen

Wir hängen das neue Element als Blatt an die erste verfügbare Position (soweit oben wie möglich, soweit links wie möglich). Dann lassen wir es nach oben "blubbern", bis es die richtige Position gefunden hat, also größer ist als das Element in seinem Eltern-Knoten.

Hier ist der Pseudo-code dafür:

# Pseudo-code für das Einfügen eines neuen Elementes in einen Heap
insert(newLabel, heap):                        
  create new leaf v at lowest and left-most position
  label(v) := newLabel
  while v != root and label(u) < label(parent(v)):                        
      swap label(v) and label(parent(v))
      v := parent(v)

Die Wurzel extrahieren

Dazu nehmen wir das letzte Element des Heaps (ganz unten, ganz rechts), löschen den Knoten und schieben das Element in den Wurzelknoten. Um die Heap-Eigenschaft wieder herzustellen, lassen wir jetzt das Element von der Wurzel nach unten fallen, bis es seinen richtigen Platz gefunden hat. Das heißt, solange ein Kind ein kleineres Element hat, vertauschen wir es mit dem kleineren der beiden Kinder.

# Pseudo-code für das Extrahieren der Wurzel in einen Heap
removeRoot(heap):    
  result := label(root(heap))                    
  swap label(root) and label(last element of heap) 
  delete last element of heap)
  v := root
  while v has a child w with label(v) > label(w):                        
      swap label(v) with label(w) (or with label(w') in case v has another child w' with label(w') < label(w))
      v := w
  return result 

Hier nun eine vollständige Darstellung von Heapsort an einem Beispiel:

Hier finden Sie eine Animation von Heapsort.

Laufzeitanalyse

Sei \(n\) die Länge des zu sortierenden Arrays. Der Heap hat zu jedem Zeitpunkt höchstens \(n\) Knoten. Was ist also die maximale Höhe? Ein Binärbaum mit 7 Knoten hat drei Ebenen, also Höhe 2; mit 8 Knoten sind es schon vier Ebenen und somit Höhe 3. Wenn wir das verallgemeinern, so schließen wir: ein fast vollständiger Binärbaum mit \(n\) Knoten hat Höhe von

Bei jeder Einfügeoperation lassen wir das Element nach oben treiben; auf jeder Ebene kann es maximal eine Vergleichsoperation geben, und auf Ebene 0 (sollte das Element bis zur Wurzel hochgeschwommen sein) gibt es keine Vergleichsoperation mehr. Daher gibt es maximal \(d\) Vergleichsoperationen. Insgesamt braucht das Aufbauen des Heaps also maximal

Vergleichsoperationen. Wie schaut es mit dem Abbau des Heaps aus? Wenn wir ein Element \(x\) in die Wurzel stecken und es dann nach unten sinken lassen, dann sinkt \(x\) von oben (Tiefe 0) bis maximal Tiefe \(d\). In jedem Schritt werden maximal zwei Vergleichsoperationen durchgeführt: zwischen den Kindern von \(x\) und zwischen dem "Sieger" und \(x\) selbst. Wenn \(x\) Tiefe \(d\) erreicht hat, werden keine weiteren Vergleiche durchgeführt, da es seinen richtigen Platz gefunden hat. Es werden also für Ebenen \(0, 1, \dots, d-1\) jeweils zwei Vergleichsoperationen gemacht, also insgesamt \(2d\). Die Gesamtzahl, addiert über alle Entfernungsoperationen, ist also maximal

Wir folgern:

Implementierung von Heapsort

Vielleicht fürchten Sie, Heapsort sei schwierig zu implementieren, weil wir ja erst einmal eine Datenstruktur für Binärbäume brauchen, also wie in Elm

type BinaryTree a
    = Empty 
    | Branch a BinaryTree BinaryTree

Das ist glücklicherweise nicht der Fall. Da unsere Heaps immer fast vollständige Binärbäume sind, gibt es eine besonders einfache Repräsentierung. Tun wir so, als hätten wir von Anfang an einen fast vollständigen Binärbaum mit \(n\) Knoten, von denen aber noch nicht alle Knoten gefüllt sind (manche stecken noch im Array):

Als nächstes numerieren wir die Zellen des Arrays und die Knoten des Binärbaumes durch, von 0 bis \(n-1\):

Jetzt können wir einfach den Heap (die blauen Zahlen) im Array in den jeweiligen Zellen abspeichern:

Um jetzt aber den Algorithmus laufen lassen zu können, brauchen wir eine einfache Formel, um von einem Knoten \(x\) (nun einfach eine Zelle im Array) zum Elternknoten \(y\) zu kommen. Hier ist sie:

Und gerade beim Abbau des Heaps müssen wir für einen Knoten \(k\) auch die Indizes der Kinder berechnen:

Ein Knoten mit Index \(k\) hat also einen Elternknoten mit Index \(\floor{k-1}{2}\) (außer \(k=0\), dann ist es die Wurzel); darüberhinaus hat \(k\) Kinder mit Index \(2k+1\) und \(2k+2\), sofern diese Indizes noch im Rahmen sind. So hat beispielsweise Knoten 3 im obigen Beispiel nur Kind 7 und eben nicht Kind 8, weil das ganze Array nur acht Elemente hat und daher nur Indizes \(0, \dots, 7\) überhaupt verwendet werden.