Übungen zu Entwicklung objekt-orientierter Bibliotheken
Blatt 4 (14. 11. - 21. 11. 2000)

Aufgabe 5 (10 Punkte)

• Eintragen eines Tupels, das aus einer ganzen Zahl (Datentyp INTEGER) und einem Objekt (eine beliebige Erweiterung von Objects.Object) besteht.
• Abfrage nach dem Tupel mit dem niedrigsten eingetragenen Wert.
• Entfernen des Tupels mit dem niedrigsten Wert.

Entwickeln Sie dann eine Implementierung dieser Abstraktion, die Termine mit einer geeigneten Datenstruktur verwaltet und alle Operationen unterstützt.

Benötigt werden solche Datenstrukturen insbesondere in der Ereignis-Simulation, im Scheduling-Bereich und unter UNIX beispielsweise von dem cron-Prozeß. Es gibt in der Literatur eine Reihe interessanter Datenstrukturen und zugehöriger Algorithmen, die für diese Aufgabenstellung geeignet sind. Auch wenn eine einfache Lösung für diese Aufgabe genügt, seien hier als Anregung drei Literatur-Referenzen genannt, die alle in unserer Informatik-Bibliothek zu finden sind:

• Michael J. Fischer and Michael S. Paterson, "Fishspear: A Priority Queue Algorithm", Journal of the Association for Computing Machinery, Vol. 41, No. 1, January 1994, pp. 3-30.
• Kehsiung Chung, Janche Sang and Vernon Rego, "A Performance Comparison of Event Calendar Algorithms: an Empirical Approach", Software--Practice and Experience, Vol. 23, No. 10, October 1993, pp. 1107-1138.
• W.R. Franta and Kurt Maly, "An Efficient Data Structure for the Simulation Event Set", Communications of the ACM, Vol. 20, No. 20, August 1977, pp. 596-602

Dies ist eine Übungsaufgabe, aus der auch ein ernsthaftes Bibliotheksprojekt entstehen kann, wenn einer der interessanteren Algorithmen in einem geeigneten Bibliotheksmodul zur Verfügung gestellt wird.