Binomial Queues (binomial heaps)

Um binomial Queues betrachten zu können, definieren wir zunächst ihre nichttrivialen Bestandteile: Binomialbäume

Definition: Die Binomialbäume sind rekursive wie folgt definiert:

Achtung: Binomialbäume sind keine Binärbäume! Wie in folgender Darstellung dieser Bäume deutlich wird, hat B_n an der Wurzel Grad n.
Binomialbäume haben folgende Zerlegungseigenschaften:

Lemma: Ein B_n läßt sich wie folgt zerlegen:

(1)

(2)

Beweis:

• zu 1: Induktion unter Verwendung der Definition von Binomialbäumen
• zu 2: Siehe Zerlegung (1) für Binomialbäume
• zu 3: Siehe Zerlegung (2) für Binomialbäume
• zu 4: Induktion über n:

  I)

  n=0 : B₀ hat 1 Knoten in Tiefe i=0 und Knoten in Tiefe i>0, also $\binom{0}{i}$Knoten in Tiefe i

  II)

  Ist N_iⁿ die Anzahl der Knoten in Tiefe i in B_n, so gilt unter der entsprechenden Induktionsannahme für B_n, daß
  $N_i^{n+1} = N_i^n + N_{i-1}^n = \binom{n}{i} + \binom{n}{i-1}$

$\Diamond$

Bemerkung: Eine mögliche Implementierung von Binomialbäumen ist das Schema ``Pointer zu Kind 1. und zum nächsten Geschwister``.

Definition: Eine Binomial Queue mit N Elementen wird wie folgt aufgebaut:

1.

Betrachte die Binärdarstellung bin(N) von N

2.

Für jedes gesetzte Bit (``1``) an Position i wird ein Binomialbaum vom Type B_i benötigt. Dieser hat bekanntlich 2ⁱ Knoten

3.

Verbinde die Binomialbäume in einer doppelt verketteten zirkulären
Liste.

4.

Beachte, daß innerhalb jedes Binomialbaums die Minimumsvariante der Heap-Bedingung, nämlich VATER$\leq$SOHN erfüllt sein muß. Dadurch ist die Wurzel eines einzelnen Binomialbaums gleichzeitig sein minimales Element.

5.

Richte einen Min-Pointer auf das Element in der Wurzel-Liste mit minimalem Schlüssel. Es ist dann das kleinste Element von allen in der Binomial Queue

Beachte, daß Priority-Queues wegen $\mathcal{O}(n)$ für Suchen keine Suchstrukturen
sind.

Beispiel: N=11 =(1011)₂:

Operationen:

1.

IsElement : Die Heap-Bedingung wirkt sich nur auf die Anordnung der Datenelemente innerhalb jedes einzelnen Binomialbaums aus, regelt aber nicht, in welchem Binomialbaum ein gegebenes Element gespeichert sein muß. Tatsächlich kann ein Element in jedem der vorhandenen Binomialbäume stehen. Das Suchen ist hier nicht effizient implementierbar, denn im worst-case muß jedes Element eines Binomialbaums angeschaut werden. B_i enthält 2ⁱ Knoten und eine Binomial Queue mit N Elementen besitzt maximal die Binomialbäume $B_0,B_1,..B_{\log{N}-1}$. Also wären zum Suchen eines Elements schlimmstenfalls $2^0+2^1+ \dots + 2^{\log{N}-1} = N-1 = \mathcal{O}(N)$ Elemente zu betrachten. Daher wird eine gesonderte Datenstruktur, etwa ein Suchbaum, für die IsElement -Operation verwendet. Dort ist Suchen mit Zeitaufwand $\mathcal{O}(\log{n})$ möglich.

2.

Merge : Das Vorgehen für das Merge zweier Vorrangwarteschlangen entspricht genau der Addition zweier Binärzahlen: Ein einzelnes B_i wird übernommen, aus zwei B_is wird ein B_i+1 konstruiert. Damit die Heap-Bedingung erhalten bleibt, wird als Wurzel des entstehenden Binomialbaums B_i+1 die kleinere der Wurzeln der beiden B_i genommen (*). Allerdings kann ein solcher Übertrag dazu führen, daß im nächsten Verschmelzungsschritt drei B_i+1 zu verschmelzen sind. Dann wird unter Beobachtung obiger Regel ein B_i+2 gebildet, und der verbleibende B_i+1 unverändert gelassen.

Algorithmus:

		 for i:= 0,1,2,3,.. do
		 		 if $(\exists$ genau 3 Bis) then
		 		 		 erzeuge/verbinde Bi+1 nach (*) und behalte ein Bi;
		 		 elseif $(\exists$ genau 2 Bis) then
		 		 		 erzeuge Bi+1 nach (*) ;
		 		 elsif $(\exists$ ein Bi) then
		 		 		 behalte es;
		 		 fi
		 od  

Komplexität: Binomial Queue Nr. 1 mit N₁ Elementen hat $\leq \log{N_1}$Binomialbäume, und analog hat Binomial Queue Nr. 2 mit N₂ Elementen $\leq \log{N_2}$Binomialbäume. Sei N:=N₁+N₂. Ein einzelner Merge -Vorgang, das Zusammenhängen zweier Binomialbäume erfolgt in konstanter Zeit. Natürlich muß er so oft ausgeführt werden, wie Binomialbäume in der resultierenden Binomial Queue vorliegen. Diese Anzahl wiederum ist höchstens $\log{N}$.

3.

Insert : Die Insert -Operation wird einfach durch Merge -Operation implementiert. Die Vorrangswarteschlange, die neu hinzukommt, ist trivial. Sie enthält nur einen Binomialbaum B₀.

1 1 1 1

(B₇) (B₄) (B₂) (B₀) 1

1 1 1 1 1

4.

Initialisierung einer Binomial-Queue durch N sukzessive Insert -Operationen:
Kosten mit $\mathcal{O}(n\log{n})$ schlecht abgeschätzt. Dabei möge sowohl das Einfügen dieses neuen einelementigen Baum als auch jede rekursive Verschmelzungsschritt eine Zeiteinheit kosten, denn jede dieser Operationen ist von der Komplexität $\mathcal{O}(1)$. Wir sind an den gesamten Kosten zum Aufbau einer Binomial Queue mit N Elementen interessiert. Dies sind übrigens identisch zum Aufwand für das binäre Hochzählen von 0 bis N, wenn jeder Zählschritt und jeder Übertrag eine Zeiteinheit kosten:

$\underbrace{\underbrace{\underbrace{\underbrace{\underbrace{0+1}_1+1}_{2\text{ Schritte}}+1}_1+1}_3+1}_1$

Sei a_n die Anzahl der Schritte (Einfügen des neuen Elements und anschließende Verschmelzungen) beim Mergen eines Knotens zu einer Queue mit (n-1) Elementen. Dann gilt für a_n:

n a_n

1 2

..4 1 3

..8 1 2 1 4

..16 1 2 1 3 1 2 1 5

..32 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6

Man erkennt sofort, daß die h-te Zeile von der Länge 2^k ist, und alle Elemente der Zeilen 1,2,..,(k-1) enthält, wobei das letzte Element um eins erhöht ist. Daraus ergeben sich folgende Rekursionsgleichungen für a_n:

$$\begin{split} a_1 & = 1 \\ a_n & = a_{\frac{n}{2}} +1 \tex... ...= a_{n-2^{\lfloor \log{n} \rfloor}} \text{ sonst}\\ \end{split}$$

Diese Bestimmungsgleichung ist unmittelbar einsichtig, denn für $n\in 2^{\mathbbm{N}_0}$ unterscheidet sich die Situation von n=2ⁱ Knoten nur insofern von der Situation mit $\frac{n}{2} = 2^{i-1}$Knoten, daß im ersten Fall noch ein Binomialbaum B_i-1 vorliegt. Das Hinzunehmen eines weiteren Knotens löst in beiden Fällen die selbe Folge von Verschmelzungsschritten aus, mit der Einschränkung, daß im letzteren Fall der neu entstandenen Baum B_i-1 mit dem vorhandenen zu einem B_i vereinigt wird. Das ist die ``+1`` in $a_n = a_\frac{n}{2} +1$. Im Falle $n\not\in 2^{\mathbbm{N}_0}$ liegen ähnliche Verhältnisse vor. Zwei Queues mit n bzw. ($n-2^{\lfloor \log{n} \rfloor}$) Knoten unterscheiden sich nur um einen Baum $B_{\lfloor \log{n} \rfloor}$. Gesucht ist nun $S_n := \Sigma_{k=1}^n a_k$. Statt obige Rekursionsgleichungen zu expandieren und eine explizite Darstellung für a_n zu suchen, die dann aufsummiert wird, betrachten wir einfach S_2^k. Obiger Tabelle sieht man an, daß S_2^k=S_2^k-1+1 gilt. Substituiert man S_2^k durch T_k und löst man die entstehene Rekursionsgleichung T_k = 2T_k-1+1, so ergibt sich T_k = 2^k+1-1, also S_n= 2n-1. Folglich ist:

5.

FindMin : Diese Operation ist trivial ausführbar, denn es ist ein Pointer auf das minimale Element gegeben. Daher ist auch die Zeitkomplexität $\mathcal{O}(1)$.

6.

DeleteMin :Das Minimum ist auf Grund der Heapbedingung Wurzel eines Binomialbaums B_k in der Liste. Wird es gelöscht, so zerfällt der Binomialbaum in k Teilbäume $B_0,B_1,\dots,B_{k-1}$

Die Teilbäume $B_0,B_1,\dots,B_{k-1}$ sind alle zur verbleibenden Queue zu mergen. Außerdem muß der Min-Pointer aktualisiert werden. Der Zeitaufwand für DeleteMin -Operation ist:

7.

Delete : Lösche Knoten x:

1-Fall)

x ist min-Wurzel: s.o.

2-Fall)

x ist eine andere Wurzel in der Wurzelliste. Analog zu oben, ohne den Min-Pointer zu aktualisieren.

3-Fall)

x sei nicht Wurzel eines Baumes:
Angenommen, x ist in Baum B_i enthalten:

Im Fall-3 muß unterschieden werden:

3a)

x ist Wurzel:

Siehe (2-Fall)

3b)

x ist in Wurzel des B_i:

So lange 3-te Fall wiederholen (Rekursiv), bis Fall-3a) eintritt

Insgesamt muß die Binomial-Queue ohne B_i mit einer aus $B_0,\cdots,B_{N-1}$ bestehenden Binomial-Queue vereinigt werden.

8.

DecreaseKey : Verkleinere Key(x)

1-Fall)

x ist die min-Wurzel: keine Strukturänderung nötig

2-Fall)

x ist eine andere Wurzel: keine Strukturänderung nötig

3-Fall)

Sonst wie Delete(x) , aber einfügen des Baumes mit Wurzel x und den neuen Key(x) in die Wurzelliste.