Algorithmentheorie 15 – Fibonacci-Heaps

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