====== Binomial-Heaps ======

Auch Binomial-Heaps können zur Implementierung einer [[struct:queue:priority_queue|Priority-Queue]] verwendet werden. Dabei handelt es sich um eine Menge von Bäumen, die gewöhnlich [[struct:heap:min-heap|Min-Heap]]-geordnet sind. Diese Heaps sind [[struct:tree:binomial-tree|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 [[struct:list:zyklisch_verkettet|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.

===== Opertionen =====

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)''

==== Heaps vereinigen ====

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.

<code>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
</code>

**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

==== Knoten einfügen ====

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.

<code>function insert(heap, node):
    tmp = neuer Heap mit node
    return union(heap, tmp)
</code>

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

==== Minimum entfernen ====

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.

<code>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
</code>

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

==== Schlüssel veringern ====

Das Verringern des Schlüssels erfolgt analog zu ''decreaseKey'' für [[struct:heap:min-heap|Min-Heaps]].

==== Knoten entfernen ====

Auch das Entfernen eines Knotens erfolgt analog zu ''delete'' für [[struct:heap:min-heap|Min-Heaps]].