heap di fibonacci
DESCRIPTION
heap di Fibonacci. heap di Fibonacci. Una heap di Fibonacci é un insieme di alberi (non necessariamente binomiali) con l’ordinamento parziale a heap. Gli alberi hanno una radice ma non sono ordinati. - PowerPoint PPT PresentationTRANSCRIPT
![Page 1: heap di Fibonacci](https://reader035.vdocumenti.com/reader035/viewer/2022062722/56813afe550346895da396df/html5/thumbnails/1.jpg)
heap di Fibonacci
![Page 2: heap di Fibonacci](https://reader035.vdocumenti.com/reader035/viewer/2022062722/56813afe550346895da396df/html5/thumbnails/2.jpg)
2/36
heap di Fibonacci
Una heap di Fibonacci é un insieme di alberi (non necessariamente binomiali) con l’ordinamento parziale a heap.
Gli alberi hanno una radice ma non sono ordinati.
Hanno una struttura meno vincolata delle heap binomiali, permettendo di differire il lavoro di riorganizzazione della struttura.
![Page 3: heap di Fibonacci](https://reader035.vdocumenti.com/reader035/viewer/2022062722/56813afe550346895da396df/html5/thumbnails/3.jpg)
3/36
heap di Fibonacci - Esempio
39
18 52
323 7
41
38 30
17
35
26 46
24
min(H)
I nodi rossi sono nodi marcati, cioè nodi che hanno perso un figlio dall’ultima volta in cui erano diventati loro stessi figli di un altro nodo.Si accede all’albero da un puntatore al nodo con chiave minima (il nodo minimo)
![Page 4: heap di Fibonacci](https://reader035.vdocumenti.com/reader035/viewer/2022062722/56813afe550346895da396df/html5/thumbnails/4.jpg)
4/36
heap di Fibonacci - Esempio
39
18 52
323 7
41
38 30
17
35
26 46
24
min(H)
Campi di ogni nodo:keydatadegpchildleftrightmark
![Page 5: heap di Fibonacci](https://reader035.vdocumenti.com/reader035/viewer/2022062722/56813afe550346895da396df/html5/thumbnails/5.jpg)
5/36
heap di Fibonacci – creazione
Make-Fib-Heap alloca e restituisce una heap di Fibonacci H, per la quale n[H]=0 e min[H]=NIL.
![Page 6: heap di Fibonacci](https://reader035.vdocumenti.com/reader035/viewer/2022062722/56813afe550346895da396df/html5/thumbnails/6.jpg)
6/36
inserimento di un nuovo nodo
inserisce un nodo x nella heap H
Fib-Heap-Insert(H,x)deg[x]=0p[x]=NILchild[x]=NILleft[x]=xright[x]=xmark[x]=FALSEconcatena la lista delle radici contenente x con la lista delle radici di Hif min[H] == NIL or key[x]<key[min[H]]then min[H] = xn[H]=n[H]+1
![Page 7: heap di Fibonacci](https://reader035.vdocumenti.com/reader035/viewer/2022062722/56813afe550346895da396df/html5/thumbnails/7.jpg)
7/36
heap di Fibonacci - Insert - Esempio
39
18 52
323 7
41
38 30
17
35
26 46
24
min(H)
2
![Page 8: heap di Fibonacci](https://reader035.vdocumenti.com/reader035/viewer/2022062722/56813afe550346895da396df/html5/thumbnails/8.jpg)
8/36
heap di Fibonacci - Insert - Esempio
39
18 52
323 7
41
38 30
17
35
26 46
24
min(H)
2
![Page 9: heap di Fibonacci](https://reader035.vdocumenti.com/reader035/viewer/2022062722/56813afe550346895da396df/html5/thumbnails/9.jpg)
9/36
heap di Fibonacci - Insert - Esempio
39
18 52
323 7
41
38 30
17
35
26 46
24
min(H)
2
![Page 10: heap di Fibonacci](https://reader035.vdocumenti.com/reader035/viewer/2022062722/56813afe550346895da396df/html5/thumbnails/10.jpg)
10/36
Estrazione del nodo minimo
E’ un’operazione complicata.Realizza la ristrutturazione dell’albero.Utilizza una procedure Consolidate per ristrutturare la lista delle radici di H, che itera i due passi seguenti fino a quando ogni radice nella lista delle radici ha grado diverso:1) trova due radici x e y nella lista delle radici con lo stesso grado, dove key[x] ≤ key[y]2) collega y a x: togli y dalla lista delle radici e fallo diventare figlio di x. deg[x] cresce e mark[y] va a false.
![Page 11: heap di Fibonacci](https://reader035.vdocumenti.com/reader035/viewer/2022062722/56813afe550346895da396df/html5/thumbnails/11.jpg)
11/36
Estrazione del nodo minimo
Fib-Heap-Extract-Min(H)z = min[H]if z ≠ NILthen foreach figlio x di z do
aggiungi x alla lista delle radici di Hp[x]=NIL
togli z dalla lista delle radici di Hif z == right[z]then min[H]=NILelse min[H] = right[z]
Consolidate(H)n[H] = n[H]-1
return z
![Page 12: heap di Fibonacci](https://reader035.vdocumenti.com/reader035/viewer/2022062722/56813afe550346895da396df/html5/thumbnails/12.jpg)
12/36
heap di Fibonacci - ExtractMin - Esempio
39
18 52
323 7
41
38 30
17
35
26 46
24
min(H)
21
![Page 13: heap di Fibonacci](https://reader035.vdocumenti.com/reader035/viewer/2022062722/56813afe550346895da396df/html5/thumbnails/13.jpg)
13/36
heap di Fibonacci - ExtractMin - Esempio
39
18 5223 7
41
38
30
17
35
26 46
24
min(H)
21
![Page 14: heap di Fibonacci](https://reader035.vdocumenti.com/reader035/viewer/2022062722/56813afe550346895da396df/html5/thumbnails/14.jpg)
14/36
heap di Fibonacci - ExtractMin - Esempio
39
18 5223 7
41
38
30
17
35
26 46
2421
0 1 2 3 4
![Page 15: heap di Fibonacci](https://reader035.vdocumenti.com/reader035/viewer/2022062722/56813afe550346895da396df/html5/thumbnails/15.jpg)
15/36
heap di Fibonacci - ExtractMin - Esempio
39
18 5223 7
41
38
30
17
35
26 46
2421
0 1 2 3 4
![Page 16: heap di Fibonacci](https://reader035.vdocumenti.com/reader035/viewer/2022062722/56813afe550346895da396df/html5/thumbnails/16.jpg)
16/36
heap di Fibonacci - ExtractMin - Esempio
39
18 5223 7
41
38
30
17
35
26 46
2421
0 1 2 3 4
![Page 17: heap di Fibonacci](https://reader035.vdocumenti.com/reader035/viewer/2022062722/56813afe550346895da396df/html5/thumbnails/17.jpg)
17/36
heap di Fibonacci - ExtractMin - Esempio
39
18 52
23
7
41
38
30
17
35
26 46
2421
0 1 2 3 4
![Page 18: heap di Fibonacci](https://reader035.vdocumenti.com/reader035/viewer/2022062722/56813afe550346895da396df/html5/thumbnails/18.jpg)
18/36
heap di Fibonacci - ExtractMin - Esempio
39
18 52
23
7
41
38
30
17
35
26 46
2421
0 1 2 3 4
![Page 19: heap di Fibonacci](https://reader035.vdocumenti.com/reader035/viewer/2022062722/56813afe550346895da396df/html5/thumbnails/19.jpg)
19/36
heap di Fibonacci - ExtractMin - Esempio
39
18 52
23
7
41
38
30
17
35
26 46
24
21
0 1 2 3 4
![Page 20: heap di Fibonacci](https://reader035.vdocumenti.com/reader035/viewer/2022062722/56813afe550346895da396df/html5/thumbnails/20.jpg)
20/36
heap di Fibonacci - ExtractMin - Esempio
39
18 52
23
7
41
38
30
17
35
26 46
24
21
0 1 2 3 4
![Page 21: heap di Fibonacci](https://reader035.vdocumenti.com/reader035/viewer/2022062722/56813afe550346895da396df/html5/thumbnails/21.jpg)
21/36
heap di Fibonacci - ExtractMin - Esempio
39
18 52
23
7
41
38
30
17
35
26 46
24
21
0 1 2 3 4
![Page 22: heap di Fibonacci](https://reader035.vdocumenti.com/reader035/viewer/2022062722/56813afe550346895da396df/html5/thumbnails/22.jpg)
22/36
heap di Fibonacci - ExtractMin - Esempio
39
18
52
23
7
41
38
30
17
35
26 46
24 21
0 1 2 3 4
![Page 23: heap di Fibonacci](https://reader035.vdocumenti.com/reader035/viewer/2022062722/56813afe550346895da396df/html5/thumbnails/23.jpg)
23/36
heap di Fibonacci - ExtractMin - Esempio
39
18
52
23
7
41
38
30
17
35
26 46
24 21
min(H)
![Page 24: heap di Fibonacci](https://reader035.vdocumenti.com/reader035/viewer/2022062722/56813afe550346895da396df/html5/thumbnails/24.jpg)
24/36
Decremento di una chiaveViene decrementata al valore k la chiave del nodo x della heap H.
Fib-Heap-Decrease-Key(H,x,k)key[x] = k; y = p[x]if y ≠ NIL and key[x] < key[y]then Cut(H,x,y), Cascading-Cut(H,y)if key[x] < key[min[H]] then min[H]=x
Cut(H,x,y)togli x dalla lista dei figli di y, decrementando deg[y]aggiungi x alla lista delle radici di Hp[x] = NIL; mark[x] = FALSE
Cascading-Cut(H,y)z = p[y]if z≠NIL then if not(mark[y])
then mark[y]=TRUEelse Cut(H,y,z),Cascading-Cut(H,z)
![Page 25: heap di Fibonacci](https://reader035.vdocumenti.com/reader035/viewer/2022062722/56813afe550346895da396df/html5/thumbnails/25.jpg)
25/36
Decremento di una chiave: Esempio
39
18
52
23
7
41
38
30
17
35
26 46
24 21
min(H)
15
![Page 26: heap di Fibonacci](https://reader035.vdocumenti.com/reader035/viewer/2022062722/56813afe550346895da396df/html5/thumbnails/26.jpg)
26/36
Decremento di una chiave: Esempio
39
18
52
23
7
41
38
30
17
35
26
15
24 21
min(H)
![Page 27: heap di Fibonacci](https://reader035.vdocumenti.com/reader035/viewer/2022062722/56813afe550346895da396df/html5/thumbnails/27.jpg)
27/36
Decremento di una chiave: Esempio 2
39
18
52
23
7
41
38
30
17
35
26
15
24 21
min(H)
5
![Page 28: heap di Fibonacci](https://reader035.vdocumenti.com/reader035/viewer/2022062722/56813afe550346895da396df/html5/thumbnails/28.jpg)
28/36
Decremento di una chiave: Esempio 2
39
18
52
23
7
41
38
30
17
26
15
24 21
min(H)
5
![Page 29: heap di Fibonacci](https://reader035.vdocumenti.com/reader035/viewer/2022062722/56813afe550346895da396df/html5/thumbnails/29.jpg)
29/36
Decremento di una chiave: Esempio 2
39
18
52
23
7
41
38
30
17
2615
24 21
min(H)
5
![Page 30: heap di Fibonacci](https://reader035.vdocumenti.com/reader035/viewer/2022062722/56813afe550346895da396df/html5/thumbnails/30.jpg)
30/36
Decremento di una chiave: Esempio 2
39
18
52
23
7
41
38
30
17
2615 24
21
min(H)
5
![Page 31: heap di Fibonacci](https://reader035.vdocumenti.com/reader035/viewer/2022062722/56813afe550346895da396df/html5/thumbnails/31.jpg)
31/36
Limitazione al grado massimo
Sia D(n) il massimo grado possibile per un nodo in una heap di Fibonacci con n elementi
Se D(n) è O(lgn) allora il tempo ammortizzato di ExtractMin e Delete è O(lgn).
Per mostrarlo, l’idea è mostrare che size(x) – num. nodi contenuti nel sottoalbero radicato in x – cresce esponenzialmente in deg(x).
![Page 32: heap di Fibonacci](https://reader035.vdocumenti.com/reader035/viewer/2022062722/56813afe550346895da396df/html5/thumbnails/32.jpg)
32/36
Limitazione al grado massimo
Lemma
Sia x un nodo di una heap di Fibonacci con deg(x) = k. Siano y1, ..., yk i figli di x nell’ordine in cui erano stati collegati a x, dal meno recente al più recente. Allora deg(y1) 0 e deg(yi) i – 2 per i = 2, 3, ..., k.
![Page 33: heap di Fibonacci](https://reader035.vdocumenti.com/reader035/viewer/2022062722/56813afe550346895da396df/html5/thumbnails/33.jpg)
33/36
Limitazione al grado massimo
Numeri di Fibonacci
F0 = 0 F1 = 1 Fk = Fk – 1 + Fk – 2
Lemma
Per ogni k 0: Fk + 2 = 1 + i = 0...k Fi
![Page 34: heap di Fibonacci](https://reader035.vdocumenti.com/reader035/viewer/2022062722/56813afe550346895da396df/html5/thumbnails/34.jpg)
34/36
Limitazione al grado massimo
Lemma
Sia x un nodo in una heap di Fibonacci con deg(x) = k.Allora size(x) Fk + 2 k, dove = (1 + 5)/2.
![Page 35: heap di Fibonacci](https://reader035.vdocumenti.com/reader035/viewer/2022062722/56813afe550346895da396df/html5/thumbnails/35.jpg)
35/36
Limitazione al grado massimo
Corollario
Il massimo grado D(n) di qualsiasi nodo in una heap di Fibonacci con n nodi è O(lgn).
Dimostrazione
Sia x un nodo in una heap H con n nodi e sia k=deg[x]. Dal Lemma prec. si ha che n ≥ size[x] ≥ k. Utilizzando i logaritmi in base si ha k ≤ logn.Il grado massimo di un qualunque nodo è quindi O(lgn).
![Page 36: heap di Fibonacci](https://reader035.vdocumenti.com/reader035/viewer/2022062722/56813afe550346895da396df/html5/thumbnails/36.jpg)
36/36
heap di Fibonacci - Sommario
heap di Fibonacci
heap binomiali Heap
Min (1) (log n) or (1) (1)
ExtractMin (log n) (log n) (log n)
DecreaseKey (1) (log n) (log n)
Union (1) (log n) (n)
Insert (1) (log n) (log n)
Delete (log n) (log n) (log n)
MakeEmpty (1) (1) (1)
IsEmpty (1) (1) (1)