Upload
philip-mclaughlin
View
46
Download
0
Embed Size (px)
DESCRIPTION
Algorithmentheorie 15 – Fibonacci-Heaps. Tobias Lauer. Fibonacci-Heaps als „lazy“ Binomial Queues. Verschmelze Bäume nur dann, wenn ohnehin alle Wurzeln betrachtet werden müssen Lasse auch Bäume zu, die keine Binomialbäume sind. 7. 2. 19. 11. 13. 45. 8. 24. 15. 36. 21. 83. 52. - PowerPoint PPT Presentation
Citation preview
WS 2006-07
Algorithmentheorie
15 – Fibonacci-Heaps
Tobias Lauer
2 WS 2006-07
Fibonacci-Heaps als „lazy“ Binomial Queues
Verschmelze Bäume nur dann, wenn ohnehin alle Wurzeln betrachtet werden müssen
Lasse auch Bäume zu, die keine Binomialbäume sind
2 19
13 45 8
36 21
24
15 83 52
79
117
3 WS 2006-07
Fibonacci-Heaps: Operationen
Q.initialize:
Q.root = null
Q.insert(e):
F = new F-Heap(e)
Q.meld(F)
Zeit = O(1)
4 WS 2006-07
Fibonacci-Heaps: deletemin
Q.deletemin():
1. Entferne den min-Knoten und hänge stattdessen die Liste seiner Söhne in die Wurzelliste ein.
2. Gehe die Wurzelliste durch:
(a) bestimme den neuen Minimalknoten
(b) „konsolidiere“ dabei die Liste, d.h. verbinde Bäume mit gleichem Wurzelgrad (link) Lösche dabei evtl. vorhandene Markierungen der Knoten, die zu Söhnen eines anderen werden.
5 WS 2006-07
deletemin: Beispiel
2 19
13 45 8
36 21
24
15 83 52
79
117
6 WS 2006-07
deletemin: Beispiel
19
24
83 52
79
117 13 45 8
36 2115
7 WS 2006-07
deletemin: Beispiel
19
24
83 52
79
117 13
45
8
36 2115
8 WS 2006-07
deletemin: Beispiel
19
24
83 52
79
117
1345
8
36 21
15
9 WS 2006-07
deletemin: Beispiel
19
24
83 52
79
117
1345 8
36 2115
10 WS 2006-07
Kosten von deletemin
Das eigentliche Entfernen geht in O(1)
Kosten hängen im Wesentlichen vom Konsolidierungsprozess ab,d.h. von der Länger der Wurzelliste und der Anzahl der notwendigen link-Operationen
Wie lässt sich das Konsolidieren effizient bewerkstelligen? Beobachtungen:
Jeder Wurzelknoten muss mindestens einmal betrachtet werden
Am Ende darf es für jeden möglichen Rang höchstens einen Knoten geben
11 WS 2006-07
consolidate: Beispiel
1913 45 8
36 21 2415
83 52
117
0 1 2 3 4 5Rang-Array:
12 WS 2006-07
consolidate: Beispiel
1913 45 8
36 21 2415
83 52
117
0 1 2 3 4 5Rang-Array:
13 WS 2006-07
consolidate: Beispiel
19
13 45 8
36 21
24
15
83 52
117
0 1 2 3 4 5Rang-Array:
14 WS 2006-07
consolidate: Beispiel
19
13
45 8
36 21
24
15
83 52
117
0 1 2 3 4 5Rang-Array:
15 WS 2006-07
consolidate: Beispiel
19
13 45
8
36 21
24
15
83 52
117
0 1 2 3 4 5Rang-Array:
16 WS 2006-07
consolidate: Beispiel
19
13 45
8
36 21
24
15
83 52
117
17 WS 2006-07
Kosten von deletemin
Vorläufig:
O(maxRank(n)) + #links
Dabei ist maxRank(n) der höchstmögliche Array-Eintrag, d.h. der größtmögliche Wurzelgrad („Rang“).
Im worst case ist #links = n – 1 Aber dies kann nur unter bestimmten Voraussetzungen eintreten!
Amortisierte Analyse liefert realistischere Laufzeitabschätzung
18 WS 2006-07
Fibonacci-Heaps: decreasekey
Q.decreasekey(FibNode N, int k):
Setze den Schlüsselwert von N auf k herab.
Wenn die Heap-Bedingung nicht mehr erfüllt ist (k < N.parent.key):
Trenne N von seinem Vater ab (mit cut) und hänge ihn (rechts vom Minimalknoten) in die Wurzelliste ein
Falls der Vater markiert ist (N.parent.mark == true), trenne auch ihn von seinem Vater ab; wenn auch dessen Vater markiert ist, trenne auch diesen ab usw. („cascading cuts“)
Markiere den Knoten, dessen Sohn zuletzt abgetrennt wurde (sofern dieser kein Wurzelknoten ist).
Aktualisiere den Minimum-Zeiger (falls k < min.key).
19 WS 2006-07
Beispiel für decreasekey
6 5
13 45 8
36 21
24
15 83 52
117
64
64
Setze den Schlüssel 64 auf 14 herab.
20 WS 2006-07
Beispiel für decreasekey
6 5
13 45 8
36 21
24
15 83 52
117
64
14
21 WS 2006-07
Beispiel für decreasekey
6 5
13 45 8
36 21
24
15 83 52
117
64
14
22 WS 2006-07
Beispiel für decreasekey
6 5
13 45 8
36
21
24
15 83 52
117
64
14
23 WS 2006-07
Beispiel für decreasekey
6 5
13 45 8
36
21
24
15 83 52
117
64
14
24 WS 2006-07
Kosten von decreasekey
Schlüssel neu setzen und Vergleich mit Vater: O(1) Abtrennen vom Vaterknoten und in Wurzelliste: O(1) Cascading cuts: #cuts Markieren des letzten Knotens: O(1)
Kosten hängen von der Anzahl der „cascading cuts“ ab.
Im worst case kann auch #cuts = n – 1 sein.Dafür muss aber eine ganz bestimmte Folge von Operationen vorangegangen sein.
Amortisierte Analyse betrachtet Laufzeit einer Operation im Kontext der vorangegangenen Operationen!
25 WS 2006-07
Amortisierte Analyse – Potentialmethode
Ordne jedem Zustand i der Datenstruktur einen Wert Фi (Potential) zu
Die amortisierten Kosten ai der i-ten Operation sind definiert als
ai = ci + (Фi – Фi-1)
d.h. die tatsächlichen Kosten zuzüglich der Änderung des Potentials, die durch die i-te Operation herbeigeführt wird.
Für Fibonacci-Heaps definieren wir Фi = wi + 2∙mi mit wi = Zahl der Wurzelknotenund mi = Zahl der markierten Knoten, die nicht Wurzeln sind
26 WS 2006-07
Potential: Beispiel
2 5
13 45 8
36 21
24
15 83 52
117
64
64
wi =
mi =
Фi =
27 WS 2006-07
Potentialmethode: Kosten von insert
Insert: Füge den neuen Knoten in die Wurzelliste ein
tatsächliche Kosten: ci = O(1)
Potential erhöht sich um 1, also Фi – Фi-1 = 1
Amortisierte Kosten: ai = ci + 1
28 WS 2006-07
Potentialmethode: Kosten von decreasekey
Tatsächliche Kosten: ci = O(1) + #cascading cuts
Potentialänderung:wi wi-1 + 1 + #cascading cutsmi mi-1 + 1 – #cascading cuts
Фi – Фi-1 = wi + 2∙mi – (wi-1 +2∙mi-1)= wi – wi-1 + 2∙(mi – mi-1) 1 + #cascading cuts + 2∙(1 – #cascading cuts)= 3 – #cascading cuts
Amortisierte Kosten: ai = ci + (Фi – Фi-1)
O(1) + #cascading cuts + 3 – #cascading cuts
29 WS 2006-07
Potentialmethode: Kosten von deletemin
Tatsächliche Kosten: ci = O(maxRank(n)) + #links
Potentialänderung:wi = wi-1 – 1 + rank(min) – #links wi-1 + maxRank(n) – #linksmi mi-1
Фi – Фi-1 = wi + 2mi – (wi-1 + 2mi-1)= wi – wi-1 + 2(mi – mi-1) maxRank(n) – #links
Amortisierte Kosten: ai = ci + (Фi – Фi-1)
O(maxRank(n)) + #links + maxRank(n) – #links
30 WS 2006-07
Bestimmung von maxRank
maxRank(n) ist die maximal mögliche Zahl von Söhnen, die ein Knoten in einem Fibonacci-Heap mit n Elementen haben kann.
Wir wollen zeigen, dass diese Zahl durch O(log n) beschränkt ist.
Umgekehrt bedeutet dies, dass jeder Knoten eine Mindestzahl an Nachfahren haben muss, die exponentiell in der Anzahl seiner Söhne ist.
31 WS 2006-07
Berechnung von maxRank(n)
Lemma 1:
Sei N ein Knoten in einem Fibonacci-Heap und k = N.rank. Betrachte die Söhne C1, ..., Ck von N in der Reihenfolge, in der sie (mit link) zu N hinzugefügt wurden. Dann gilt: (1) C1.rank ≥ 0 (2) Ci.rank ≥ i - 2 für i = 2, ..., k
Beweis: (1) klar
(2) Als Ci zum Sohn von N wurde, waren C1, ..., Ci-1 schon Söhne von N, d.h. es war N.rank ≥ i-1. Da durch link immer Knoten mit gleichem Rang verbunden werden, war beim Einfügen also
auch Ci.rank ≥ i-1. Seither kann Ci höchstens einen Sohn verloren haben (wegen cascading cuts), daher muss gelten:
Ci.rank ≥ i - 2
32 WS 2006-07
Berechnung von maxRank(n)
Lemma 2:
Sei N ein Knoten in einem Fibonacci-Heap und k = N.rank. Sei size(N) = die Zahl der Knoten im Teilbaum mit Wurzel N.
Dann gilt: size(N) ≥ Fk+2 ≥ 1.618k
D.h. ein Knoten mit k Söhnen hat mind. Fk+2 Nachkommen (inkl. sich selbst).
Beweis: Sei Sk = min {size(N) | N mit N.rank = k}, d.h. die kleinstmögliche Größe eines Baums mit Wurzelrang k. (Klar: S0 = 1 und S1 = 2.)Seien wieder C1, ..., Ck die Söhne von N in der Reihenfolge, in der sie zu N hinzugefügt wurden.
Es ist size(N) ≥ Sk =
33 WS 2006-07
Berechnung von maxRank(n)
Beweis: Sei Sk = min {size(N) | N mit N.rank = k}, d.h. die kleinstmögliche Größe eines Baums mit Wurzelrang k. Seien wieder C1, ..., Ck die Söhne von N in der Reihenfolge, in der sie zu N hinzugefügt wurden.
Es ist size(N) ≥ Sk =
13
36
21
10
3214
61
34 WS 2006-07
Berechnung von maxRank(n)
Erinnerung: Fibonacci-Zahlen
F0 = 0 F1 = 1 Fk+2 = Fk+1 + Fk für k ≥ 0
Die Folge der Fibonacci-Zahlen wächst exponentiell mit Fk+2 ≥ 1.618k
Es gilt außerdem: Fk+2 =
(einfacher Beweis durch vollständige Induktion über k.)
k
iiF
2
2
35 WS 2006-07
Zusammenfassung
Es ist außerdem S0 = 1 = F2 und S1 = 2 = F3
Damit ist klar: Sk = Fk+1 (Beweis per Induktion)
Für einen Knoten N mit Rang k ist also
size(N) Sk = Fk+1 ≥ 1.618k
k
iik FF
22 2
k
iik SS
222
36 WS 2006-07
Berechnung von maxRank(n)
Satz:
Der maximale Rang maxRank(n) eines beliebigen Knotens in einem
Fibonacci-Heap mit n Knoten ist beschränkt durch O(log n).
Beweis: Sei N ein beliebiger Knoten eines Fibonacci-Heaps mit n Knoten und sei k = N.rank.
Es ist n ≥ size(N) ≥ 1.618k (nach Lemma 2)
Daher ist k ≤ log1.618(n) = O(log n)
37 WS 2006-07
Zusammenfassung
Lineare Liste (Min-)Heap Fibonacci-Heap
insert: O(1) O(log n) O(1)
min: O(n) O(1) O(1)
deletemin: O(n) O(log n) O(log n)*
decreasekey: O(1) O(log n) O(1)*
delete: O(n) O(log n) O(log n)*
*Amortisierte Kosten