Analyse

Lemma 1

Der Aufruf makeHeap(f) macht aus f einen Heap, das heißt für alle $i=0,...,k$ gilt $f[i]\geq f[2i+1]$ und $f[i]\geq f[2i+2]$ , wobei $k=(f.length-2)/2$ ist.

Beweis

Der Beweis erfolgt durch Induktion nach i=f.length-1.

i=0: Ein ein-elementiges Array ist stets ein Heap nach Definition

i‐1‐>i: Nach Induktionsvoraussetzung ist f[0..i‐1] ein Heap. In der Methode siftUp(f,idx) wird zunächst das neue Element mit seinen Eltern verglichen. Ggfs. werden die Werte getauscht und es wird bottom-up fortgefahren. Da ein Knoten dadurch höchstens einen größeren Wert erhält bleibt die Heap‐Eigenschaft bestehen.

Lemma 2

Ist f[0...i‐1] ein Heap bei dem maximal für den Wurzelknoten die Heap‐Eigenschaft verletzt ist, so ist nach reHeap(f,i‐1) das Array f[0...i‐1] ein Heap.

Beweis

In reHeap wird zunächst der Wurzelknoten mit seinen beiden Kindern verglichen. Ist der Wert der Wurzel nicht kleiner als die Werte beider Kinder, so terminiert die Methode. Damit ist f[0...i‐1] ein Heap. Andernfalls wird der Wert der Wurzel mit dem größten Wert seiner Kinder vertauscht, die Heap‐Eigenschaft ist damit an der Wurzel wiederhergestellt. Anschließend wird iterativ mit dem vertauschten Kind fortgefahren. Nach Induktion folgt dann, dass f[0...i‐1] am Ende ein Heap ist.

Theorem 1

Der Algorithmus heapSort löst das Problem des vergleichsbasierten Sortierens.

Beweis

Folgt direkt aus den vorherigen beiden Lemmata und der Beobachtung, dass in jedem Schritt der heapSort‐ Methode das größte Element an das Ende des Arrays getauscht wird und nur noch ein um eins verkleinertes Array betrachtet wird.

Theorem 2

Der Algorithmus heapSort(f) terminiert für jede Eingabe f nach endlicher Zeit.

Beweis

Die Hauptmethode heapSort verfügt über eine konstante Anzahl an Schleifendurchläufen. In jedem rekursiven Aufruf von makeHeap wird der Index echt verringert, bei Index 0 ist der Rekursionsanfang erreicht. In reHeap wird die Variable current in jedem Durchgang um mindestens 1 erhöht und bei Erreichen von „end“ wird abgebrochen.

Theorem 3

Der Algorithmus heapSort hat einen Aufwand von O(n log n), sowohl für den besten, schlechtesten, und mittleren Fall.

Beweis

Für makeHeap gilt: Wir fügen jeden der n Knoten dazu

Auf jeden Knoten wird siftUp ausgeführt – möglicherweise bis zum Wurzelknoten
Da der Binärbaum perfekt balanciert ist, benötigt siftUp() auf einem einzelnen Knoten O(log n) Zeit
Weil wir das n‐mal machen, benötigen wir n*O(log n) viel Zeit, d.h. O(n log n)

Für

for(int i = f.length - 1; i > 0; i--){
   swap(f,0,i);
   reHeap(f,i-1); 
}

gilt:

Die Schleife wird n‐mal (genauer n‐1 mal) durchlaufen,weil wir immer einen der n Knoten entfernen
Entfernen und Ersetzen des Wurzelknotens beansprucht O(1) viel Zeit
Deswegen beträgt die Gesamtzeit n, für das Entfernen und Ersetzen (ohne reHeap)
Um reheap auf den Wurzelknoten auszuführen, müssen wir einen Pfad von der Wurzel bis zu einem Blattknoten verfolgen (eventuell können wir früher aufhören)
Der Binärbaum ist perfekt balanciert
Deswegen ist dieser Pfad O(log n) lang
- Und wir führen nur O(1) Operationen auf jedem Knoten aus
- Deswegen benötigt reheap O(log n) viel Zeit
Weil wir reheap innerhalb einer while‐Schleife ausführen, benötigen wir hierfür O(n log n) Die Gesamtzeit ist deswegen: O(n log n) + O(n log n) = O(n log n)

Literatur

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 14.6.1 zu finden.