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

4.3 Die Minimum Suchen-Funktion


Einleitung Die Funktion "Minimum Suchen" ermittelt das im Priority Queue gespeicherte Element mit der höchsten Priorität. Dazu muß sie in einem Binomial Heap das Element ausfindig machen, dessen Schlüssel den kleinsten Wert hat.

Das Minimum Suchen - Applet Versuche nun im folgenden Applet das Minimum im dargestellten Binomial Heap zu finden. Dazu stehen Dir folgende Funktionen zur Verfügung:
Baum
Mit dieser Funktion kannst du zur Wurzel des nächsten Binomialbaums gelangen..
Bruder
Mit dieser Funktion kannst du zum eventuell vorhandenen linken Bruderknoten gelangen.
Vater
Mit dieser Funktion kannst du zum Vaterknoten des aktuellen Knotens gelangen.
Merken
Hat der aktuelle Knoten einen kleineren Wert als das bisherige Minimum, so kannst du dir mit dieser Funktion das neue Minimum merken.
Sohn
Hat der aktuelle Knoten mindestens einen Sohn, so kannst du mit dieser Funktion zum rechten Sohn gelangen.
Fertig
Mit diesem Button kannst du dem Applet mitteilen, daß du das Minimum gefunden und gemerkt hast. Dir wird dann mitgeteilt, ob dies auch wirklich das Minimum ist, oder ob du noch weiter suchen mußt.
Neu
Mit der Neu-Funktion kannst du das Applet in die Ausgangssituation zurücksetzen.
Oben links kannst du den Wert des bisher ermittelte Minimums erkennen. Weiterhin ist das momentan von Dir betrachtete Element rot und das bisherige Minimum grau dargestellt. Suche nun das Minimum des Binomial Heaps:

Das Bauen - Applet

Die Minimum Suchen - Funktion Wie du vielleicht bemerkt hast, werden in dem obigen Applet die Funktionen "Bruder", "Sohn" und "Vater" nicht benötigt, um das Minimum des Binomial Heaps zu finden. Denn die einzelnen Bäume des Binomial Heap sind heapgeordnet, weshalb sich das kleinste Elementen des jeweiligen Binomialbaumes an dessen Wurzel befinden muß. Um das kleinste Element des gesamten Heaps finden zu können, müssen deshalb nur die Wurzeln der Bäume miteinander verglichen werden und das kleinste dieser Elemente ist automatisch auch das kleinste Element des gesamten Heaps.

Die hier kennengelernte Funktion ist eine wichtige Funktion zur Verwaltung eines Priority Queues und wird von den Funktion "Minimum Entfernen" und "Entferne Element" verwendet werden. Als nächstes soll nun die Funktion "Minimum Entfernen" behandelt werden.

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