Kurs:Algorithmen und Datenstrukturen/Vorlesung/Heap Sort Analyse
Analyse
BearbeitenLemma 1
BearbeitenDer Aufruf makeHeap(f) macht aus f einen Heap, das heißt für alle gilt und , wobei ist.
![{\displaystyle f[i]\geq f[2i+1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/acfcf18c9c2d05c62fc6ecca32e6ae415d19b977)
![{\displaystyle f[i]\geq f[2i+2]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/222847e0cfe1e3660e7201e75f09219fb6035ade)
Beweis
BearbeitenDer 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
BearbeitenIst 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
BearbeitenIn 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
BearbeitenDer Algorithmus heapSort löst das Problem des vergleichsbasierten Sortierens.
Beweis
BearbeitenFolgt 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
BearbeitenDer Algorithmus heapSort(f) terminiert für jede Eingabe f nach endlicher Zeit.
Beweis
BearbeitenDie 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
BearbeitenDer Algorithmus heapSort hat einen Aufwand von O(n log n), sowohl für den besten, schlechtesten, und mittleren Fall.
Beweis
BearbeitenFü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
BearbeitenDa 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.
