Binomial-Heaps

Auch Binomial-Heaps können zur Implementierung einer Priority-Queue verwendet werden. Dabei handelt es sich um eine Menge von Bäumen, die gewöhnlich Min-Heap-geordnet sind. Diese Heaps sind Binomial-Bäume, wobei von jedem Grad höchstens ein Binomial-Baum im Binomial-Heap existiert. Ein Binomial-Baum von Grad <m>k</m> wird mit <m>B_k</m> bezeichnet.

Die Binomial-Bäume befinden sich dabei in einer Wurzelliste (im Code als heap.rootlist bezeichnet) in Form einer zyklisch verkettete Liste. Zusätzlich besitzt ein Binomial-Heap einen Zeiger auf den Knoten in der Wurzelliste (heap.min), der den geringsten Schlüssel besitzt.

Entsprechend lassen sich auf Binomial-Heaps folgende Operationen ausführen:

• union(heap1, heap2): heap - vereinigt die Binomial-Heaps heap1 und heap2 und liefert diesen
• insert(heap, node)
• extractMin(heap): node
• decreaseKey(heap, node, key)
• delete(heap, node)

Diese Operation ist grundlegend (fast) für alle folgenden Operationen. Zunächst werden die Wurzellisten so zu einer neuen Wurzelliste verkettet, dass diese aufsteigend bezüglich des Grades der Bäume sortiert ist. Anschließend wird durch diese iteriert und paarweise Bäume gleichen Grades verknüpft. Dabei wird der eine Baum Kind der Wurzel des anderen, so dass sich der Grad des Baumes um 1 erhöht. Zu beachten ist, dass dabei jene Wurzel mit dem kleineren Schlüssel die neue Wurzel des Gesamtbaumes wird. Damit bleibt die Min-Heap-Eigenschaft erhalten.

function union(heap1, heap2):
    Erzeuge verkettete Wurzelliste H
    Durchlaufe H und verkette die Bäume gleichen Grades wie folgt:
        1. Fall: Vom Grad i ist genau 1 Baum vorhanden. Behalte ihn.
        2. Fall: Vom Grad i sind genau 2 Bäume vorhanden. Verknüpfe sie zu einem B_{i+1}.
        3. Fall: Vom Grad i sind genau 3 Bäume vorhanden. Behalte einen der beiden und
            verknüpfe die anderen zu einem B_{i+1}.
    return Heap mit Wurzelliste H

Bemerkung: In heap1 und heap2 jeweils maximal ein <m>B_i</m> und ein <m>B_{i-1}</m> existieren. Damit werden die <m>B_{i-1}</m> zu einem <m>B_i</m> verknüpft. Mehr als drei Bäume vom Grad <m>i</m> können somit nicht existiere.

Laufzeit: <m>O(ld n)</m>, wobei der neue Heap <m>n</m> Knoten besitzt

Die Idee des Einfügens ist einfach: Zunächst wird ein neuer Binomial-Heap mit einem <m>B_0</m> erzeugtt, welcher den neuen Knoten enthält. Anschließend werden beide Heaps vereinigt.

function insert(heap, node):
    tmp = neuer Heap mit node
    return union(heap, tmp)

Laufzeit: <m>O(ld n)</m>, siehe union.

Um das Minimum zu entfernen ist es notwendig das neue Minimum zu bestimmen, d.h. den Minimum-Zeiger gültig zu verändern. Das neue Minimum kann sich entweder in der Wurzelliste oder in der Kinderliste des bisherigen Minimums befinden. Daher werden alle Kinder des bisherigen Minimums zunächst in die Wurzelliste verschoben. Nun wir das aktuelle Minimum gelöscht und das neue gesucht.

function extractMin(heap)
    tmp = heap.min
    füge alle Kinder von heap.min in heap.rootlist ein
    entferne heap.min
    suche neues Minimum in heap.rootlist
    return tmp

Laufzeit: <m>O(ld n)</m>

Das Verringern des Schlüssels erfolgt analog zu decreaseKey für Min-Heaps.

Auch das Entfernen eines Knotens erfolgt analog zu delete für Min-Heaps.