Kurs:Algorithmen und Datenstrukturen/Vorlesung/Heap Sort Analyse

Startseite

Vorlesung

1.Einleitung

2. Theoretische Grundlagen

2.1 Programmierparadigmen

2.2. Laufzeitanalysen

2.3. Entwurfsmuster

3. Suchen

3.1 Suchen in sortierten Folgen

3.2 Suchen in Texten

4. Sortieren

4.1 Algorithmen für vergleichsbasiertes Sortieren

4.2 Weitere Sortierprobleme

5. Dynamische Datenstrukturen

5.1 Binäre Suchbäume

5.2 AVL Bäume

5.3 2-3-4-Bäume und Rot-Schwarz Bäume

5.4 Heaps

5.5 Hashtabellen

6. Graphen

6.1 Einführung

6.2 Breitensuche

6.3 Tiefensuche

6.4 Topologisches Sortieren

6.5 Berechnung kürzester Wege

6.6 Berechnung maximaler Flüsse

6.7 Spannbäume

7. Optimierung

7.1 Grundlagen

7.2 Kombinatorische Optimierung

7.4 Lineare Optimierung

7.5 Simplex Verfahren

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.