Binomial Heaps

Definition:
Ein Binomialbaum ist ein gerichteter Baum $B_n$ mit Sortierbedingung (2), an dessen Wurzel die Unterbäume $B_0$...$B_{n-1}$ hängen. $B_0$ besteht aus einem einzigen Knoten.

Eigenschaften:
1. Die Wurzel von $B_n$ hat Grad $n$.
2. $B_n$ hat Höhe $n$.
3. $B_n$ hat $n \choose i$ Knoten in Tiefe $n$.
4. $B_n$ hat $2^n$ 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 $B_i$ ist höchstens einmal im Heap vorhanden.

Operationen:

1. $Merge(H_1,H_2)$: Heaps als Binärzahlen mit 1, wenn $B_i \in H$, sonst 0 kodieren. Da der Merge nur verschiedene $b_i$ erzeugen darf, entspricht er genau einer Addition der beiden Binärzahlen. Im Falle, dass $B_i \in H_1$ und $B_i \in H_2$, wird daraus $B_{i+1}$ mit der kleineren der beiden Wurzeln als neue Wurzel. Im Falle eines Übertrags sind drei $B_i$ zu einem $B_{i+1}$ und einem unveränderten $B_i$ zu machen. Kosten für $N_1$ bzw. $N_2$ Bäume sind $O(N_1+N_2)$ oder bei insgesamt $n$ Elementen $O(\log n)$.

2. $Insert$: Neues $B_0$ und Merge-Operation, Kosten $O(\log n)$, amortisiert für $N$ Operationen nur $O(N)$ (z.B. beim Initialisieren mit $N$ Elementen).

3. $ExtractMin$: Minimum ausgeben, Baum $B_n$ zerfällt in $n$ Teilbäume, Merge-Operation anwenden, Zeiger auf das Minimum neu setzen, Kosten $O(\log n)$

4. $Delete$: FIXME