Dr. Andreas Borchert Sektion Angewandte Informationsverarbeitung
Ingo Melzer Blatt 8


[c]



Allgemeine Informatik II (SS 1999)


Abgabetermin 8. Juli 1999

10. Heapsort (25 Punkte)

Ein Heap ist ein spezieller binärer Baum, bei dem für jedes Element im Baum gilt, daß es kleiner ist, als seine beiden Nachfolger. Dies kann zum Sortieren von Elementen genutzt werden:

• Zuerst werden einfach alle Elemente in einen binären Baum eingelesen. Dies sollte so geschehen, daß der längste Zweig maximal eins länger ist als der kürzeste.
• Dann stellt man die Heap-Eigenschaft des Baumes her, indem man von den Blättern her nach oben steigt (Rekursion) und immer die großen Elemente sinken läßt.
• Da das kleinste Element sich jetzt sicherlich an der Wurzel befindet, kann es einfach ausgegeben werden. Damit der Heap nicht in zwei Teile zerfällt, wird nun ein am tiefsten liegendes Element nach oben gesetzt. Um die Heap-Eigenschaft zu erhalten, reicht es dieses Element wieder nach unter sinken zu lassen.
• Den dritten Schritt sollte man wiederholen - bis der Heap leer ist.

Ein möglicherweise unklarer Punkt ist das Sinkenlassen von Elementen. Dies geschieht am einfachsten, indem man das betroffene Element mit seinen beiden Nachfolgern vergleicht. Ist mindestens einer kleiner, so vertauscht man es mit dem kleinsten Nachfolger und setzt den Vorgang an der ehemaligen Position des Nachfolgers fort, bis man nicht mehr tauschen muß. Auf diesem Weg sinkt das Element an eine korrekte Position.

Schreiben Sie sich nun ein Modul Heap, das obiges leistet. Als Grundlage für Ihre Datenstruktur kann Seite 179 genutzt werden. Da dieses Modul für sich nichts tun wird (sie verwenden ja wieder Objects.Object als Basistyp für Ihre Daten), können Sie gerne mein Testmodul vom FTP-Server ziehen.

Für dieses Blattes sollten Sie das Definition-Module, das Sie auf dem FTP-Server finden, verwenden. Dieses sollte nicht verändert werden.