Hilfe Hauptseite Vorherige Naechste
Logo
Navigationsleiste
1. Der Binomial Heap Algorithmus

2. Vergleich des Binomial Heap Algorithmus
mit anderen Algorithmen


Algorithmen zur Verwaltung eines
Priority Queues
Neben dem hier vorgestellten Binomial Heap kann ein Priority Queue auch mittels einer verketteten Liste oder einem Binärbaum verwaltet werden. In diesem Kapitel soll deshalb kurz behandelt werden, wo die Stärken des Binomial Heap Algorithmus im Vergleich zu diesen einfacheren Implementierungsformen liegen. Auf die Implementierung dieser Datenstrukturen wird in diesem Abschnitt aber nicht eingegangen. Zum Studium von verketteten Listen und Binärbäumen sei deshalb auf Ottmann [Ottmann96] verwiesen.

Die verkettete Liste Die einfachste Möglichkeit zur Speicherung der Daten wäre die Verwendung einer verketteten Liste. Bräuchte für die Verwaltung von Druckaufträgen z.B. nur ein neuer Druckauftrag hinter die anderen eingereiht zu werden und würde immer nur der erste in der Warteschlange abgearbeitet, so kann diese Aufgabe mit dieser Datenstruktur mit konstantem Zeitaufwand durchgeführt werden.
Haben die zu verwaltenden Elemente aber unterschiedliche Prioritäten (z.B Anwendungsprozesse und Betriebssystemprozesse), so können neue Elemente nicht einfach an die Liste angehängt werden. In diesem Fall müßte bei jeder Einfügeoperation die richtige Stelle in der Liste gesucht werden. Das Suchen der richtigen Position benötigt aber im schlechtesten Fall N Vergleiche bei einer Liste mit N Elementen. Zwar könnten die Funktionen Initialisieren, Minimum Suchen und Minimum Entfernen mit konstantem Zeitbedarf ausgeführt werden, aber die Funktion Element Einfügen wäre für zeitkritische Anwendungen nicht effizient genug.

Der Binärbaum Für diesen Anwendungsfall wäre die Implementierung mittels eines Binärbaums effizienter zu realisieren. Mit dieser Datenstruktur hat die Funktion Element Einfügen nur noch einen logarithmischen Zeitbedarf. Zwar haben bei dieser Datenstruktur nun auch die Funktionen Minimum Suchen und Minimum Entfernen einen logarithmischen Zeitbedarf, aber da keine der Funktionen ein lineares Wachstum des Zeitbedarfs hat, ist diese Implementierungsform für einen Prozess-Queue insgesamt günstiger.
Nun kann es aber einen Anwendungsfall geben, bei dem verschiedene Priority Queues miteinander verschmolzen werden müssen. Denkbar wäre dies z.B. in einem Multi-Prozessorsystem, in dem ein Prozessor kurzfristig auch die Prozesse eines anderen Prozessors verarbeiten muß. Die dazu benötigte Verschmelzen-Funktion läßt sich aber mit Binärbäumen wieder nur mit linear wachsendem Zeitbedarf realisieren.

Der Binomial Heap Hier liegt nun die Stärke des Binomial Heap Algorithmus. Beim Binomial Heap Algorithmus besitzen die Funktionen Element Einfügen, Minimum Suchen, Minimum Entfernen und Verschmelzen alle nur noch logarithmischen Zeitbedarf.
Doch wie ist die Funktionsweise des Binomial Heap Algorithmus? Um diesen Algorithmus verstehen zu können, muß zuerst die dem Algorithmus zugrundeliegende Datenstruktur bekannt sein. Diese soll nun in Kapitel 3 ausführlicher behandelt werden.


1. Der Binomial Heap Algorithmus
Seitenanfang Vorherige Naechste
Navigationsleiste