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

4.1 Die Verschmelzen-Funktion (1)


Einleitung Wie in Kapitel 3.2 Beschrieben, ist ein Binomial Heap ein Wald von Binomialbäumen. Um nun zwei Binomial Heaps zu einem einzigen verschmelzen zu können, müssen die Binomialbäume, aus denen sich die beiden Binomial Heaps zusammensetzten, miteinander verbunden werden.

Der Sonderfall Wie die Verschmelzung konkret abläuft, soll nun erst an einem einfachen Sonderfall erläutert werden. Angenommen, die beiden zu verschmelzenden Binomial Heaps enthalten jeweils nur einen Binomialbaum Bk. Dann können sie wie in Kapitel 3.1 bereits beschrieben, zu einem Bk+1-Baum verbunden werden, indem einfach der Baum mit dem größeren Schlüssel in der Wurzel an die Wurzel des anderen Baums gehängt wird. Der resultierende Binomialbaum Bk+1, der automatisch wieder heapgeordnet ist, ist das Ergebnis der Verschmelzen-Funktion. Die folgende Grafik zeigt die beiden Ausgangs-Heaps und den resultierenden Binomial Heap:

Die Verschmelzung zweier Binomial Heaps Auch bei der normalen Verschmelzung zweier beliebiger Binomial Heaps werden die einzelnen Binomialbäume miteinander verbunden.

Die Probierphase Versuche nun im folgenden Applet, die beiden Binomial Heaps miteinander zu verschmelzen. Das Ergebnis soll danach in der Ergebniszeile stehen. Für die Verschmelzung stehen dir folgende Funktionen zur Verfügung:
Verbinden
Mit dieser Funktion kannst du zwei Binomialbäume miteinander verbinden.
Uebertrag
Diese Funktion ermöglicht es dir, einen Binomialbaum in die nächste Spalte zu übertragen.
Ergebnis
Soll ein Binomialbaum ins Ergebnis übernommen werden, so benutze dazu diese Funktion.
Auswahlmenü
Mit dem Auswahlmenü kannst du zwischen den verschiedenen Beispielen wählen und die aktuelle Aufgabe in den Ausgangszustand zurücksetzen.

Das Verschmelzen - Applet

Zum Standardverfahren Weiter mit der Erläuterung des Standardverfahrens.

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