TU Wien:Algorithmen und Datenstrukturen 1 VU (Raidl)/Übungen SS09/Beispiel 9
Zur Navigation springen
Zur Suche springen
- Schreiben Sie einen Algorithmus in Pseudocode, der für ein gegebenes Feld A feststellt, ob dieses einen gültigen Maximum-Heap enthält (d.h., das größte Element soll in A[1] stehen usw.). Der Inhalt des Feldes darf dabei natürlich nicht verändert werden. Analysieren Sie die Laufzeit Ihres Algorithmus in -Notation
- Überprüfen Sie Ihren Algorithmus anhand der folgenden zwei Zahlenfolgen: Welche der nachstehenden Zahlenfolgen erfüllt die Heapeigenschaft, welche nicht? Zeichnen Sie zu jeder der Zahlenfolgen die entsprechende Baumdarstellung des Heaps, um ihre Antwort zu begründen.
- <15,8,12,8,4,10,1,6,4,5,3,2>
- <11,10,10,1,1,1,8,8,0,0,0>
Algorithmus[Bearbeiten | Quelltext bearbeiten]
checkMaxHeap(var A) //Eingabe: Heapfolge A //Ausgabe: Wahrheitswert, mit Aussage ob die Folge A ein MaxHeap ist //Variablen: i,x 1: x = true; 2: für i = 1,..,n/2 { 3: falls A[i] < A[2i] ODER A[i] < A[2i+1] dann { 4: x = false; 5: break; 6: } 7: } 8: retourniere x;
Analyse des Algorithmus[Bearbeiten | Quelltext bearbeiten]
Worst-Case (es ist ein MaxHeap): (n)
Best-Case (es is kein MaxHeap): (1)
Average-Case (es is nur am Anfang ein MaxHeap): (n)
Überprüfen des Algorithmus und zeichnen der Bäume[Bearbeiten | Quelltext bearbeiten]
Wie hier rot markiert, ist die Heap-Eigenschaft bei dem Eintrag "5" verletzt. Demnach kein gültiger Heap.
Ebenso hier sieht man das die Heap-Eigenschaft vom Eintrag "8" verletzt wird. Demnach auch kein gültiger Heap.