Wir betrachten einen Sortieralgorithmus, der einerseits Worstcase-Kosten von \(O(n\log n)\) hat und gleichzeitig nur \(O(1)\) Speicherplatz benötigt. Die Idee von Heapsort ist es, eine geeignete Datenstruktur — einen Heap — zu benutzen und mithilfe dieser Datenstruktur zu sortieren. Der clevere Trick hierbei ist, dass die Datenstruktur direkt im gegebenen Array realisiert werden kann. Das heißt, wir benötigen dafür keinen zusätzlichen Speicherplatz.

Bevor wir zum Sortieralgorithmus kommen, müssen wir uns also zunächst näher mit Heaps beschäftigen.

Ein besonderer gerichteter Binärbaum ist der vollständige Binärbaum. Bei ihm haben alle Knoten, außer die Knoten im letzten Level, genau zwei Kinder und die Knoten im letzten Level haben gar keine Kinder.

Die Struktur eines Min- bzw. Max-Heaps ist der eines vollständigen Binärbaums sehr ähnlich: Ein Min/Max-Heap hat die Struktur eines Binärbaums, der bis zum vorletzten Level vollständig ist und das letzte Level von links her gefüllt sein muss. (Wir werden später sehen, warum wir diese Eigenschaft unbedingt benötigen.) Außerdem muss in einem Min-Heap die Min-Heap-Eigenschaft gelten und in einem Max-Heap die Max-Heap-Eigenschaft. Die Min-Heap-Eigenschaft besagt, dass der Schlüsselwert eines Elternknotens immer höchstens so groß ist, wie der Schlüsselwert jedes seiner Kinder. Analog gilt für die Max-Heap-Eigenschaft, dass der Schlüsselwert eines jeden Elternknotens immer mindestens so groß sein muss, wie der Schlüsselwert jedes seiner Kinder.

Aus diesen Eigenschaften folgt direkt, dass die Wurzel eines Min-Heaps den kleinsten Schlüsselwert, d. h. das Minimum über alle Schlüssel, enthalten muss. Bei einem Max-Heap enthält die Wurzel das Maximum über alle Schlüssel.

Man beachte auch, dass für die Schlüsselwerte der Kinder eines Knotens in einem Min/Max-Heap nur gilt, dass ihre Schlüsselwerte mindestens/höchstens so groß sind, wie die ihres Elternknotens — jedoch wird nicht gefordert, dass das linke Kind den kleinsten/größten Schlüsselwert aller Kinder hat oder ähnliches. Die Min/Max-Heap-Eigenschaft sagt nur etwas darüber aus, wie sich die Schlüsselwerte von direkt benachbarten Knoten verhalten, über die Schlüsselwerte innerhalb eines Levels wird nichts ausgesagt. (Solche Aussagen werden wir später noch bei Suchbäumen antreffen.)

Um mit Min/Max-Heaps zu arbeiten, müssen wir uns überlegen, wie wir aus einer Folge von Schlüsselwerten einen korrekten Min/Max-Heap erzeugen können. Das wird die Operation BuildMinHeap bzw. BuildMaxHeap erledigen. Außerdem wollen wir in einem Min-Heap das Minimum entfernen, d. h., die Operation ExtractMin umsetzen, und in einem Max-Heap das Maximum entfernen, d. h., die Operation ExtractMax implementieren. (Später werden wir Min-Heaps benutzen, um damit spezielle Queues zu konstruieren und dazu noch die Operationen Insert und DecreaseKey hinzufügen.)

Wir wollen das folgende Problem lösen:

Gegeben: Ein Array \(A\) mit \(n\) Schlüsselwerten.

Aufgabe: Konstruiere aus \(A\) einen korrekten Min/Max-Heap, der alle Schlüsselwerte von \(A\) enthält.

Das Problem kann man mit den folgenden zwei Schritten sehr elegant lösen:

1. Erzeuge einen Binärbaum mit der richtigen Form, wobei die Knoten die Schlüssel aus dem Array \(A\) enthalten.
2. Teste für jeden Knoten, ob die Min/Max-Heap-Eigenschaft gilt. Falls sie nicht gilt, dann stelle sie her.

BuildMinHeap(\(A\))

Input: Array \(A\) der Länge \(n\)
Output:Min-Heap mit allen Elementen aus \(A\)

1. erzeuge Binärbaum \(T\) der richtigen Form, der in jedem Knoten genau einen Schlüsselwert von \(A\) enthält
2. for Level=vorletztes Level to erstes Level
3.     for Knoten=rechtester Knoten in Level to linkester Knoten in Level
4.         MinVersickere(Knoten)
5.     end for
6. end for
7. return \(T\)

Hierbei ist bei Zeile \(1\) eben genau ein bis zum vorletzten Level vollständiger gerichteter Binärbaum gemeint, bei dem das letzte Level von links her gefüllt ist. Wichtig ist, dass wir mit MinVersickere beim rechtesten Knoten im vorletzten Level beginnen, d. h. beim rechtesten Knoten im vorletzten Level von \(T\).

Nun klären wir noch, was genau MinVersickere tut. Wir betrachten den Code und ein Beispiel parallel:

Analog definieren wir BuildMaxHeap, wobei dort statt MinVersickere die Subroutine MaxVersickere genutzt wird:

Danach sind wir fertig. Es wurde für alle Elternknoten ab dem vorletzten Level einmal MinVersickere aufgerufen. Offensichtlich hängen die Kosten von BuildMinHeap somit sehr stark von den Kosten für MinVersickere ab. Die sind jedoch leicht zu ermitteln. Die Höhe eines Knotens \(i\) in einem gerichteten Binärbaum sei die Anzahl der Kanten auf dem längsten Pfad von Knoten \(i\) zu einem Blatt des Baums, wobei jeder Schritt des Pfads immer von einem Elternknoten zu einem Kind dieses Knotens geht. Im obigen Min-Heap wäre die Höhe des Knotens mit Schlüssel \(12\) genau \(2\), da z. B. der Pfad \(12 \to 18 \to 25\) maximal lang ist und zu einem Blatt führt. Die Höhe eines Blattes ist immer \(0\).

Mithilfe der Höhe eines Knotens können wir leicht die Kosten von Min/MaxVersickere bestimmen: Die Kosten von Min/MaxVersickere(Knoten \(i\)) sind in \(\mathcal{O}(\)Höhe von Knoten \(i)\). Der Grund hierfür ist, dass für jede Kante auf dem Weg von Knoten \(i\) zum tiefsten Blatt, das unterhalb von \(i\) liegt, eine Vertauschung der Schlüsselwerte erfolgen kann. Außerdem kann jeweils der kleinste/größte Schlüsselwert der maximal zwei Kinder eines Elternknotens in konstanter Zeit ermittelt werden.

Die Operationen der Queue sind jeweils konstant und wir können leicht mit einem Zeiger durch das Array laufen, um die entsprechenden Schlüsselwerte auszulesen.

Nun analysieren wir, was in der for-Schleife passiert. Wir wollen eine obere Schranke zeigen und nehmen deshalb an, dass wir für maximal viele Knoten MinVersickere aufrufen und jeder Aufruf so teuer wie möglich ist. Wir haben uns bereits überlegt, dass die Kosten von MinVersickere für einen Knoten mit Höhe \(k\) in \(\Theta(k)\) liegen, das heißt, die Kosten sind höchstens \(c\cdot k\) für eine Konstante \(c\). Für unsere obere Schranke müssen wir uns somit nur noch überlegen, wie viele Knoten wir versickern und welche Höhe sie jeweils haben, und dann addieren wir alle Kosten einfach auf.

Bei BuildMinHeap beginnen wir im vorletzten Level des Binärbaums und im schlimmsten Fall sind dort alle Knoten auch Elternknoten und jeder Elternknoten hat genau zwei Kinder. Wir nehmen also an, dass auch das letzte Level vollständig gefüllt ist. Mit Hilfe von Lemma 1 gilt deshalb \(n = \sum_{i=0}^h 2^i = 2^{h+1}-1\), wobei \(h\) die Höhe der Wurzel ist. Außerdem gilt, dass das vorletzte Level genau \(2^{h-1}\) Knoten enthält, das vorvorletzte \(2^{h-2}\) usw. bis zum \(0\)-ten Level, das nur die Wurzel und somit \(2^0\) Knoten enthält.

Die Knoten im \(0\)-ten Level, d. h. nur die Wurzel, haben Höhe \(h\) und somit kostet das Versickern der Wurzel höchstens \(c\cdot h\). Die Knoten im ersten Level haben Höhe \(h-1\) und somit kostet das Versickern pro Knoten in diesem Level höchstens \(c \cdot (h-1)\). Allgemein gilt, dass Knoten im Level \(i\), für \(0\leq i \leq h-1\), eine Höhe von genau \(h-i\) haben und somit das Versickern pro Knoten in Level \(i\) höchstens \(c \cdot (h-i)\) kostet.

Wir haben uns bereits überlegt, dass es höchstens \(\frac{n}{2^{i}}\) viele Knoten mit Höhe \(i\) gibt.

Für Anzahl der Knoten mit Höhe \(h\) gilt folgendes: Sei \(n(h)\) die Anzahl der Knoten mit Höhe \(h\). Aus Lemma 1 folgt, dass \[n(h) \leq \frac{n}{2^h}\ .\]

Seien \(C(n)\) die Kosten von BuildMinHeap auf einem Array mit \(n\) Elementen, wobei \(2^{h}-1 < n \leq 2^{h+1}-1\). Dann gilt:

\[C(n) \leq \sum_{i=0}^{h-1} 2^{i} \cdot c \cdot (h-i) = c \cdot \sum_{i=0}^{h-1} 2^{i} \cdot (h-i) \leq c \cdot \sum_{i=0}^{h-1} \frac{n}{2^{h-i}}\cdot (h-i)\] \[ = cn \cdot \sum_{i=0}^{h-1} \frac{h-i}{2^{h-i}} = cn \cdot \left(\frac{h}{2^h} + \frac{h-1}{2^{h-1}} + … + \frac{h-(h-1)}{2^{h-(h-1)}} \right) = cn \cdot \sum_{i = 1}^{h} \frac{i}{2^i}\ . \]

Es gilt

Und damit folgt \( \sum_{i=1}^h \frac{i}{2^i} < \sum_{i=0}^\infty \frac{i}{2^i} \leq {1} + {\frac{1}{2}} + {\frac{1}{4}} + … = \sum_{i=0}^\infty \frac{1}{2^i} = 2\). Hierbei haben wir mehrfach die bereits bekannte geometrische Reihe \(\sum_{i=0}^\infty \frac{1}{2^i} = 2\) genutzt.

Damit haben wir bewiesen, dass \(C(n) \leq cn \cdot 2 \in O(n)\) gilt.

Wir müssen uns daher etwas cleverer anstellen. Die Lösung liegt darin, dass wir dafür sorgen, dass am Ende das richtige Blatt, nämlich das rechteste im letzten Level, gelöscht wird. Das erreichen wir, indem wir die folgenden Schritte ausführen:

Nun, da wir Heaps kennen, können wir sie nutzen, um zu sortieren. Wir betrachten zunächst die einfachste Variante von Heapsort. Diese Version wird schon eine Worstcase-Laufzeit von \(O(n\log n)\) haben. Allerdings benötigen wir auch noch \(\Theta(n)\) zusätzlichen Speicherplatz. Der Code lautet wie folgt:

 Die Analyse ist nun sehr einfach. Zeile \(1\) kostet uns \(O(n)\). Jeder der \(n\) vielen Durchläufe der for-Schleife kostet höchstens \(O(\log n)\). Somit haben wir insgesamt Kosten in \(O(n\log n)\) im Worstcase. Neben dem Array \(A\) wird allerdings noch \(\Theta(n)\) Speicherplatz für den Min-Heap benötigt. Das heißt, diese Version von Heapsort benötigt recht viel zusätzlichen Speicherplatz.

Somit können wir auch einfach ein Array mit \(n\) Elementen als einen gerichteten Binärbaum mit \(n\) Knoten auffassen, der bis zum vorletzten Level vollständig ist und dessen letztes Level von links her gefüllt ist. (Das ist der eigentliche Grund, warum das letzte Level eines Heaps von links her gefüllt sein muss.) Das Element an Index \(0\) ist die Wurzel, das linke Kind davon steht an Index \(2\cdot 0 +1 = 1\), das rechte Kind steht an Index \(2\cdot 0 + 2 = 2\) usw. Wir benötigen also den Binärbaum überhaupt nicht!

Nun müssen wir nur noch unsere Version von Min/MaxVersickere auf die Array-Implementierung anpassen:

Für ArrayMaxVersickere müssen lediglich die Ungleichungen in Zeile \(6\) und \(10\) umgedreht werden. Man beachte, dass wir neben dem Index \(i\), der das zu versickernde Element bezeichnet, auch noch einen Index \(j\) mitgeben. Dieser Index markiert den letzten Eintrag im Array, d. h. den rechtesten Knoten im letzten Level des zugehörigen Heaps. Eigentlich ist das unnötig, wenn wir wissen, wie viele Elemente das Array hat. Doch mit diesem Trick müssen wir das nicht jedes Mal abfragen.

Nun kommen wir noch zur neuen Version von BuildMinHeap(\(A\)):

Man beachte, dass an Index \(\lfloor\frac{n}{2}\rfloor -1\) der rechteste Elternknoten im vorletzten Level steht. Es genügt, bei ihm zu beginnen und sich dann Level für Level nach oben, jeweils von rechts nach links, zu arbeiten. Genau diese Reihenfolge erhalten wir auch, wenn wir die Nummerierung umgekehrt ablaufen.

Wir haben eben gesehen, dass wir das Eingabearray auch direkt als Heap auffassen können. Damit gelingt es uns, Heapsort mit nur konstant viel Zusatzspeicher zu realisieren. Allerdings benötigen wir dazu noch einen Trick: Wir werden statt eines Min-Heaps einen Max-Heap verwenden! Außerdem benötigen wir ExtractMin/Max überhaupt nicht. Uns genügt ArrayBuildMaxHeap und ArrayMaxVersickere.

Wir benutzen einen Max-Heap, da wir ja eigentlich nach und nach Elemente aus dem Heap entfernen wollen. Im Array bedeutet das, dass wir uns die hintersten Elemente nicht mehr anschauen, da sie dann nicht mehr zum Heap gehören. Wenn wir aber aufsteigend sortieren wollen, dann müssen in den hinteren Zellen des Arrays aber die größten Werte stehen! Und genau die liefert uns ein Max-Heap.

Zu beachten ist, dass in Zeile \(4\) von ArrayHeapsort jeweils in einem Max-Heap versickert wird, der einen Knoten weniger, nämlich den jeweils rechtesten Knoten im letzten Level, enthält. Das ist genau der Index, zu dem wir das aktuelle Maximum getauscht haben. Damit wird verhindert, dass das so eben getauschte Maximum wieder nach oben rückt.

Min/Max-Heaps werden häufig als Implementierung einer Priority-Queue genutzt. Eine Priority-Queue ist jede Datenstruktur, die die Operationen Insert (ein neues Element mit einem Prioritätswert einfügen), ExtractMin (das Element mit der kleinsten/größten Priorität entfernen und ausgeben) und DecreaseKey (den Prioritätswert eines Elements verringern/erhöhen) unterstützt.

Wir haben bereits ExtractMin behandelt. Es fehlen noch Insert und DecreaseKey.

DecreaseKey können wir auch leicht in \(\Theta(\log n)\) ausführen, sofern wir einen Zeiger direkt auf den entsprechenden Knoten (bzw. den Index bei Arrayimplementierung) im Min/Max-Heap haben. Diese Zeiger zu verwalten ist leicht. Wir können sie einfach als weiteres Attribut an jedes Knotenobjekt im Graphen schreiben. Mithilfe dieses Zeigers können wir somit direkt auf den zu ändernden Schlüssel im Min/Max-Heap zugreifen. Nach Änderung müssen wir dann wie bei Insert evtl. noch nach oben versickern.

Heapsort sortiert, indem ein Heap genutzt wird, um iterativ jeweils das größte bzw. kleinste Element zu ermitteln. Ein solcher Min/Max-Heap kann in Linearzeit aufgebaut werden. Und falls wir irgendwo eine Schlüsseländerung haben, z. B. durch einen Tausch, dann kann in logarithmischer Zeit die Min/Max-Heap-Eigenschaft wieder hergestellt werden.

Wenn wir Heaps clever implementieren, dann können wir sie direkt im Eingabearray speichern und somit auf zusätzlichen Speicher verzichten. Die Laufzeit von Heapsort ist für jede Eingabe (mit unterschiedlichen Schlüsselwerten) in \(O(n\log n)\), da immer in \(\Theta(n)\) ein Heap aufgebaut wird und dann jeweils \(n\)-mal versickert wird. Versickern kostet höchstens \(O(\log n)\).

Wenn wir Heaps als Priority-Queue nutzen, dann können wir damit leicht die Operationen Insert, ExtractMin und DecreaseKey jeweils in \(O(\log n)\) realisieren.