Definition:
Ein Binomialbaum ist ein gerichteter Baum mit Sortierbedingung (2),
an dessen Wurzel die Unterbäume ... hängen. besteht aus einem einzigen Knoten.
Eigenschaften:
1. Die Wurzel von hat Grad .
2. hat Höhe .
3. hat
Knoten in Tiefe .
4. hat Knoten.
Definition:
Ein Binomial Heap (Binomial Queue) ist eine zyklisch verkettete Liste von Binomialbäumen
mit einem Zeiger auf den Baum mit minimalem Element (höchster Priorität).
Jeder Binomialbaum vom Typ ist höchstens einmal im Heap vorhanden.
Operationen:
1. : Heaps als Binärzahlen mit 1, wenn , sonst 0 kodieren. Da der Merge nur verschiedene erzeugen darf, entspricht er genau einer Addition der beiden Binärzahlen. Im Falle, dass und , wird daraus mit der kleineren der beiden Wurzeln als neue Wurzel. Im Falle eines Übertrags sind drei zu einem und einem unveränderten zu machen. Kosten für bzw. Bäume sind oder bei insgesamt Elementen .
2. : Neues und Merge-Operation, Kosten , amortisiert für Operationen nur (z.B. beim Initialisieren mit Elementen).
3. : Minimum ausgeben, Baum zerfällt in Teilbäume, Merge-Operation anwenden, Zeiger auf das Minimum neu setzen, Kosten
4. : FIXME