Binomial-Heap

Verschmelzen zweier Binomialbäume von Grad 2: Vergleiche die Wurzeln und füge dem Baum mit kleinerer Wurzel (grau) den anderen Baum (schwarz) als linken Teilbaum hinzu. Am Ende erhält man so den unteren Baum mit Grad 3.

Die zentrale Operation ist das Verschmelzen zweier Heaps (merge), da diese als Unterprogramm aller anderen Operationen verwendet wird. Die Operation erfolgt ähnlich der bitweisen Addition von Dualzahlen. In diesem Fall entspricht dies der Addition der Anzahl der Elemente n₁ und n₂ der zu verschmelzenden Heaps.

Dazu werden simultan die Listen der beiden Heaps beginnend bei den Bäumen niedrigster Ordnung durchlaufen. In einer speziellen Variablen wird – ähnlich der bitweisen Addition – ggf. ein Übertrag (in Form eines Baumes) festgehalten. Anfangs ist dieser Übertrag leer.

Sei nun x die höchste Binärstelle von ${\displaystyle n_{1}+n_{2}}$ verschieden von 0, das heißt ${\displaystyle x=\log _{2}(n_{1}+n_{2}+1)-1}$. Zu jeder natürlichen Zahl k mit ${\displaystyle 0\leq k\leq x}$ wird nun in aufsteigender Reihenfolge die Anzahl der Bäume mit Ordnung k in beiden Heaps und in der Übertragsvariablen betrachtet. Ist diese

• 0, so passiert nichts.
• 1, so wird der entsprechende Baum in den neuen Heap übernommen und der Übertrag ggf. geleert.
• 2, so wird der Baum, dessen Schlüssel an der Wurzel größer ist, zum am weitesten links stehenden Kind des anderen Baumes gemacht und der so entstehende Baum der Ordnung k+1 als Übertrag behalten.
• 3, so wird der Baum aus dem Übertrag in den neuen Heap übernommen und von den beiden Bäumen in den Heaps wird der Baum, dessen Schlüssel an der Wurzel größer ist zum am weitesten links stehenden Kind des anderen Baumes gemacht und der so entstehende Baum der Ordnung k+1 als Übertrag behalten.

Jeder dieser Schritte lässt sich in konstanter Zeit durchführen. Da maximal ${\displaystyle \log _{2}(n_{1}+n_{2}+1)}$ derartige Schritte getätigt werden, benötigt die Operation im schlimmsten Fall nur logarithmisch viel Zeit.

Aufspalten eines Binomial-Baumes mittels split. Dreiecke symbolisieren die neuen Teilbäume. Die Beschriftung der Knoten bezeichnet deren Ordnung vor beziehungsweise nach dem Aufspalten. Es gilt k>a₁>a₂>...>a_i=x, wobei i+1 die Tiefe von Knoten X im Baum ist.

Neben merge ist das Entfernen eines Elementes (remove) die anspruchsvollste Operation. Sei X das zu entfernende Element, seine Ordnung x und T der Binomial-Baum, der dieses Element enthält und dessen Ordnung k beträgt. Ausgehend von X muss der Binomial-Baum, der das Element enthält, geeignet in kleinere Binomial-Bäume aufgespalten werden. Dieses Aufspalten des Baumes geschieht am einfachsten mit einer rekursiven Funktion split, der als Argument ein Knoten im Baum übergeben wird. Anfangs ist X selbst das Argument. Sofern das übergebene Argument einen Elternknoten besitzt, ruft sich die Funktion zuerst selbst mit diesem als Argument auf und entfernt anschließend solange das am weitesten links stehende Kind des Vaters – also das Kind mit höchster Ordnung – bis das Argument selbst aus dem Baum entfernt wurde.

Da das Entfernen des am weitesten links stehenden Elementes gerade die umgekehrte Operation zum oben dargestellten rekursiven Aufbau der Binomial-Bäume darstellt, sind die so abgespaltenen Bäume und der Rest weiterhin Binomial-Bäume. Ferner ist X nun Wurzel eines Baumes und es lässt sich zeigen, dass der ursprüngliche Baum nun in genau 2 Binomial-Bäume der Ordnung x sowie in jeweils einen Binomial-Baum der Ordnung x+1, x+2, ..., k-1 zerfallen ist. Werden nun noch in gleicher Weise alle Kinder von X entfernt, so ist X vollständig isoliert und kann problemlos gelöscht werden. Dabei entsteht aus den Kindern für jedes j in {0, ..., x-1} jeweils genau ein Binomial-Baum der Ordnung j. Insgesamt bleibt also für jedes j aus {0, ..., k-1} ein Binomial-Baum der Ordnung j übrig. Diese Bäume bilden zusammen wieder einen Binomial-Heap, der mittels merge mit dem Rest des Heaps verschmolzen werden kann.

Das Abspalten des am weitesten links stehenden Elementes ist in konstanter Zeit möglich. Da der ursprüngliche Baum genau k mal aufgespalten wird, der Binomial-Heap aber mindestens 2^k Elemente enthält, benötigt diese Operation im Worst-Case nur logarithmisch viel Zeit. Da das anschließende merge selbst auch nur logarithmisch viel Zeit benötigt ist auch die Gesamtlaufzeit im schlimmsten Fall logarithmisch zur Anzahl der Elemente im Heap.

Die übrigen Operationen gestalten sich nun sehr einfach.

• Um ein neues Element einzufügen (insert), wird einfach ein neuer Heap erzeugt, der nur dieses eine Element enthält und dieser mittels merge mit dem eigentlichen Heap verschmolzen.
• Um ein Element mit minimalem Schlüssel zu entnehmen (extractMin), braucht lediglich das Minimum der Wurzeln gefunden zu werden, indem die Liste der Wurzeln einmal durchlaufen wird und das gefundene Element mit remove entfernt und zurückgegeben wird.
• Um den Schlüssel eines Elementes zu verändern (changeKey) wird dieses mit remove zunächst entfernt, dann dessen Schlüssel geändert und anschließend mit insert wieder eingefügt.