Hilfe Hauptseite Vorherige Naechste
Logo
Navigationsleiste
1. Der Binomial Heap Algorithmus / 4. Die Funktionen

4.4 Die Minimum Entfernen-Funktion


Einleitung Dieser Funktion dient dazu, das als nächstes zu verarbeitende Element aus dem Binomial Heap zu entfernt. Dazu muß sie in einem Binomial Heap das kleinste im Binomial Heap gespeicherte Element finden und dann dieses aus dem Binomial Heap entfernen.

Die Minimum Entfernen- Funktion Zur Ermittlung des im Binomial Heap gespeicherten Minimums kann die Minimum Entfernen-Funktion auf die in Kapitel 4.3 vorgestellte "Minimum Suchen"-Funktion zurückgreifen.
Folgende Grafik zeigt einen Binomial Heap FN nach Ausführung der Minimum Suchen-Funktion mit dem selektierten Minimum in Baum Bi:


Nachdem durch die Minimum Suchen-Funktion das zu entfernende Element gefunden wurde, wird der zugehörige Binomialbaum Bi zur weiteren Bearbeitung aus dem Binomial Heap genommen. Übrig bleibt ein neuer Binomial Heap F'N, welcher dem Binomial Heap FN ohne Bi entspricht:


Dann wird in dem Baum Bi die Wurzel (also das Minimum) entfernt, wodurch dieser Baum in seine Teilbäume Bi-1 , ... , B0 zerfällt:


Diese Teilbäume Bi-1 , ... , B0 bilden nun einen neuer Binomial Heap F''N. Um zum gewünschten Ergebnis der Minimum Entfernen-Funktion zu gelangen, muß nun der neue Binomial Heap F''N nur noch unter Verwendung der in Kapitel 4.1 vorgestellten "Verschmelzen"-Funktion mit dem Binomial Heap F'N verschmolzen werden. Folgende Grafik zeigt das Endergebnis der Ausführung der Minimum Entfernen - Funktion:


Das
Minimum Entfernen - Applet
Entferne nun nach der oben beschriebenen Methode im folgenden Applet das Minimum aus dem dargestellten Binomial Heap. Dazu stehen dir folgende Funktionen zur Verfügung:
Min. Suchen
Mit der "Minimum Suchen"-Funktion kannst du im Binomial Heap nach dem Minimum suchen.
Wurzel Ent.
Diese "Wurzel Entfernen"-Funktion ermöglicht es dir, aus einem Binomialbaum die Wurzel zu entfernen.
Fertig
Mit dieser Funktion kannst du überprüfen, ob die Funktion "Minimum Entfernen" von dir vollständig ausgeführt wurde.
Verschm.
Mittels der "Verschmelzen"-Funktion ist es dir möglich, zwei Binomial Heaps miteinander zu verschmelzen.
Baum Ent.
Mit der "Baum Entfernen"-Funktion kann ein Binomialbaum aus dem Binomial Heap entfernt werden.
Auswahlmenü
Mit dem Auswahlmenü kannst du zwischen den verschiedenen Beispielen wählen und die aktuelle Aufgabe in den Ausgangszustand zurücksetzen.

Das Entfernen - Applet

Zusammenfassung Die komplexe Minimum Entfernen-Funktion kann also die Funktionen "Minimum Suchen" und "Verschmelzen" verwenden.
Mit den bisher vorgestellten Funktionen läßt sich der Binomial Heap schon zur Verwaltung eines Priority Queues verwenden. Nach der Initialisierung des Priority Queues mit der "Initialisieren"-Funktion (Kapitel 4) können neue Elemente mit der Funktion "Element Einfügen" (Kapitel 4.2) in den Priority Queue eingefügt werden. Mit der Funktion "Minimum Entfernen" kann dann das als nächstes zu bearbeitende Element im Priority Queue ermittelt werden.

Aber die Funktion "Element Entfernen" zum Entfernen eines beliebigen Elements aus dem Priority Queue könnte noch nützlich sein. Denn wenn z.B. eine Anwender nach Abschicken eines Druckauftrags in den Queue und noch vor dessen Ausführung beschließt, daß dieser Druckauftrag abgebrochen werden soll, sollte der Druckauftrag jederzeit aus dem Priority Queue entfernt werden können. Oder wenn eine Anwendung vom Benutzer beendet wird, sollte der Prozeß jederzeit aus dem Priority Queue zur Prozeßverwaltung entfernt werden können.
Um die Funktion "Entferne Element" implementieren zu können, muß nun aber zuerst in Kapitel 4.5 die Funktion "Verkleinere Schlüssel" eingeführt werden.

1. Der Binomial Heap Algorithmus / 4. Die Funktionen
Seitenanfang Vorherige Naechste
Navigationsleiste