TU Wien:Algorithmen und Datenstrukturen 1 VU (Raidl)/Übungen SS09/Beispiel 9

• 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 $\Theta$-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

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,..,$\lfloor$n/2$\rfloor$ {
 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

Worst-Case (es ist ein MaxHeap): $\Theta$(n)

Best-Case (es is kein MaxHeap): $\Theta$(1)

Average-Case (es is nur am Anfang ein MaxHeap): $\Theta$(n)

Überprüfen des Algorithmus und zeichnen der Bäume

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.