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

4.1 Die Verschmelzen-Funktion (2)


Das Standardverfahren Vielleicht bist du beim experimentieren mit dem Probierapplet schon selbst darauf gekommen:

Die Verschmelzung zweier Binomial Heaps wird analog zur normalen Addition zweier Dualzahlen durchgeführt.

Wenn die beiden Binomial Heaps FA und FB mit jeweils A und B Elementen miteinander verschmolzen werden sollen, betrachtet die Verschmelzungsfunktion die einzelnen Binomialbäume in aufsteigender Reihenfolge, wobei mit der Stelle 0 begonnen wird. Dabei können folgende Fälle auftreten:
  1. Ist an der Stelle i in keinem der beiden Binomial Heaps ein Baum Bi vorhanden und auch kein Übertrag von i-1 zu berücksichtigen, so hat auch der resultierende Binomial Heap keinen Baum Bi.
  2. Tritt an der Stelle i nur ein Baum Bi auf, ist also entweder nur in FA, in FB oder im Übertrag ein Baum Bi vorhanden, so wird dieser Baum in den resultierende Binomial Heap übernommen und es wird kein Übertrag für die nächst höhere Stelle erzeugt.
  3. Falls an der Stelle i genau zwei Operanden auftreten, so werden diese zu einem Binomialbaum Bi+1 zusammengefaßt und als Übertrag an die nächst höhere Stelle weitergegeben.
  4. Sind schließlich an einer Stelle i alle drei Operanden vorhanden, wird ein Baum Bi in den resultierenden Binomial Heap eingefügt, und die anderen beiden werden zu einem Baum Bi+1 zusammengefügt und als Übertrag an die Stelle i+1 weitergereicht.


Ein Beispiel Folgendes Beispiel soll dieses Verfahren verdeutlichen: Seien die beiden Binomial Heaps FA und FB mit A = 5 und B = 7 Elementen gegeben. Dann ergibt die Addition von A und B im Dualsystem folgende Rechnung:



Analog dazu sieht die Verschmelzung von FA und FB wie folgt aus:



Die Übungsphase Versuche jetzt, in folgendem Applet die Verschmelzung zweier Binomial Heaps nach dem Standardverfahren durchzuführen. Dazu 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.
Tip
Mit dieser Funktion kannst du dir einen Tip geben lassen, welcher Schritt als nächstes durchzuführen ist.
Auswahlmenü
Mit dem Auswahlmenü kannst du zwischen den verschiedenen Beispielen wählen und die aktuelle Aufgabe in den Ausgangszustand zurücksetzen.

Das Verschmelzen - Applet

Die hier beschriebene Verschmelzen-Funktion ist eine grundlegende Funktion des Binomial Heap Algorithmus. Sie wird von einigen der folgenden Funktionen verwendet. Unter anderem von der als nächstes vorgestellten "Element Einfügen"-Funktion.

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