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

Aus VoWi
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.