URL:         /axel/informatik2_ss00_blatt2.html
 
 

Aufgabe 3 (6 + 5 Punkte)
Man konstruiere eine Eingabefolge der Länge 15, bei der  Heapsort  maximale Schrittzahl benötigt. Beweis.
Man gebe eine Konstruktionsvorschrift an wie man ein Feld der Länge n mit maximaler Schrittzahl bei Heapsort bekommt. Beweis
 
 
 

Aufgabe 4 (6 Punkte)
Aus einem Feld mit n=2^k-1 Elementen läßt sich wie folgt ein Heap aufbauen. Zuerst bildet man rekursiv zwei Heaps mit je 2^k-1-1 Elementen. Dann bildet man einen vollen Binärbaum, dessen Wurzel durch das verbleibene Element gegeben ist. Durch Einsinken der Wurzel ergibt sich der gewünschte Heap. Man analysiere den worst case Aufwand für das Erstellen eines Haufens. Das Ergebnis soll in O Notation in Abhängigkeit von n gegeben werden, z.B. O(n²)