Frage:binomial queues
(a) Sei
Q
der in
Binomial-Queues
(14 Punkte)
eine leere Binomial-Queue. Fügen Sie die Schlüssel
Q
4, 1, 7, 6, 2, 3, 5
nacheinan-
ein. Geben Sie die resultierenden Wälder nach jedem Aufruf von merge
an. Führen Sie anschlieÿend delete-min (Q) aus. Geben Sie dabei zuerst die durch
access-min (Q) betrachteten Elemente an. Zeichnen Sie danach die Wälder
D m
D n+m , der am Ende
merge (D n , D m ) nicht anzugeben.
und zum Schluss den Wald
Zwischenschritte von
(b) Sei
D n
und
entsteht. Sie brauchen die
Q eine leere Binomial-Queue. Geben Sie je Teilaufgabe einen Rechenweg an, um
Q
die gröÿtmögliche Anzahl einzufügender Elemente zu bestimmen, sodass
(i) aus jeweils einem Binomialbaum vom Typ
(ii) keinen Binomialbaum vom Typ
B i
B 1 , B 3 , B 5
i ≥ n
mit
B 7
und
besteht bzw.
für ein beliebiges
(c) Beschreiben Sie eine Methode für die Implementierung der Operation
die in der Binomial-Queue
Q
den Schlüssel von Element
a
k
auf
n ∈ N
enthält.
relocate(Q, a, k) ,
setzt, ohne dass
dabei Binomial-Queues gemischt bzw. Binomialbäume auseinandergenommen oder
vereinigt werden. Es soll nicht einfach
mit neuem Schlüssel für
a
delete(Q, a)
und anschlieÿend
ausgeführt werden.
Schätzen Sie die Worst-Case-Laufzeit Ihrer Lösung möglichst gut im
Aufgabe 11.2
insert(Q, k)
O -Kalkül
