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

4. Die Funktionen des Binomial Heap Algorithmus


Die Funktionen Wie bereits in Kapitel 3.2 beschrieben, werden neben dem Binomial Heap zur Speicherung der Daten auch die folgenden Funktionen benötigt, um einen Priority Queue verwalten zu können:
  • Initialisieren: Mit dieser Funktion wird einfach der leere Binomial Heap erzeugt.
  • Verschmelzen: Diese Funktion ermöglicht die Verschmelzung zweier Binomial Heaps zu einem Binomial Heap.
  • Element Einfügen: Mit dieser Funktion kann ein neues Element in den Binomial Heap eingefügt werden.
  • Minimum Suchen: Diese Funktion ermittelt das kleinste im Heap gespeicherte Element. (Z.B. kann die Priorität um so größer sein, je kleiner der Schlüssel des Elements ist)
  • Minimum Entfernen: Mit dieser Funktion wird das als nächstes zu verarbeitende Element aus dem Binomial Heap entfernt.
Unter Verwendung der oben beschriebenen Funktionen läßt sich mit Hilfe des Binomial Heaps ein Priority Queue realisieren, wobei der logarithmische Zeitbedarf dieser Funktionen die Verwendung des Binomial Heap Algorithmus zur Implementierung eines Priority Queues attraktiv macht. Sinnvoll wären aber noch folgende Funktionen:
  • Verkleinere Schlüssel: Mit dieser Funktion läßt sich der Wert des Schlüssels eines beliebigen Elements verkleinern.
  • Entferne Element: Diese Funktion ermöglicht die Entfernung eines beliebigen Elements aus dem Binomial Heap.
Denn wenn z.B. ein Anwender nach Abschicken eines Druckauftrags in den Queue und noch vor dessen Ausführung beschließt, daß dieser Druckauftrag abgebrochen werden soll, sollte er aus dem Queue entfernt werden können. Also sollte ein beliebiges Element aus dem Binomial Heap entfernt werden können und nicht nur das momentane Minimum.

Anhängigkeiten der Funktionen Einige der oben beschriebenen Funktionen können auf die Funktionalität anderer Funktionen zurückgreifen. Wie z.B. in Kapitel 4.2 gezeigt, kann die Funktion "Element Einfügen" die Funktion "Verschmelzen" verwenden. Zur Veranschaulichung der Abhängigkeiten folgt nun der Abhängigkeitsgraph der Funktionen:

Initialisieren Verschmelzen Element Einfuegen Minimum Suchen Minimum Entfernen Verkleinere Schluessel Entferne Element
Abhaengigkeitsgraph

Das Binomial Heap Applet Nachdem die oben beschriebenen Funktionen verstanden wurden, können die Funktionen "Element Einfügen" und "Minimum Entfernen" im Kapitel 4.7 mit dem Binomial Heap Applet noch einmal mit eigenen Beispieldaten ausprobiert werden.

Zuerst sollten aber die Funktionen näher kennengelernt werden. Deshalb weiter mit Kapitel 4.1.

1. Der Binomial Heap Algorithmus
Seitenanfang Vorherige Naechste
Navigationsleiste