Download - Mucchi binomiali
![Page 1: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/1.jpg)
1
Heap binomiali
Gli heap binomiali sono strutture dati su cui si possono eseguire efficientemente le operazioni:
Mucchi binomiali
Make(H) : crea un heap vuoto.Insert(H, x) : aggiunge il nodo x allo heap.
Minimum(H) : ritorna il puntatore al nodo con chiave minima. ExtractMin(H) : ritorna il puntatore al nodo con chiave minima dopo averlo tolto dallo heap.
Union(H1, H2) : riunisce due heap in un unico heap.
![Page 2: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/2.jpg)
2
DecreaseKey(H, x, k) : cambia la chiave di x con una minore.
Delete(H, x) : toglie il nodo x.
Oltre alle precedenti operazioni fondamentali degli heap riunibili, sugli heap binomiali definiremo anche le due ulteriori operazioni:
![Page 3: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/3.jpg)
3
Alberi binomiali
Gli heap binomiali sono insiemi di alberi binomiali.
Alberi binomiali
Un albero binomiale Bk di grado k è un albero ordinato (vi è un ordine tra i figli di ogni nodo) definito ricorsivamente nel seguente modo:
L’albero binomiale B0 di grado 0 è costituito da un solo nodo, la radice.
![Page 4: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/4.jpg)
4
L’albero binomiale Bk di grado k > 0 è costituito da due alberi binomiali di grado k - 1 collegati tra loro ponendo la radice del primo come primo figlio della radice del secondo.
Graficamente:
B0
Bk-1
Bk
Bk-1
![Page 5: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/5.jpg)
5
B0 B1 B2 B3 B4
![Page 6: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/6.jpg)
6
Proprietà degli alberi binomiali.L’albero binomiale Bk:
1) ha 2k nodi;2) ha altezza k;
ik3) ha esattamente nodi a livello i;
4) la radice ha grado k e tutti gli altri nodi hanno grado minore;
5) se xk-1, xk-2, ..., x0 sono i figli della radice elencati per indice decrescente da sinistra a destra allora xi è radice di un albero binomiale Bi di grado i.
![Page 7: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/7.jpg)
7
Bk
Bk-1
Bk-2
B0
B2B1
.........
Limiti conseguenti.Un albero binomiale di n = 2k nodi ha sia altezza che grado uguali a k = log2 n.
![Page 8: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/8.jpg)
8
Dimostrazione.L’albero binomiale B0: 1) ha 20 = 1 nodi;2) ha altezza 0;3) ha esattamente nodi a livello 0;4) la radice ha grado 0 e non ci sono altri nodi;5) la radice non ha figli;
100
quindi le cinque proprietà sono vere per k = 0. Assumiamole vere per k-1 e dimostriamole per k.
![Page 9: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/9.jpg)
9
2) l’altezza di Bk è uno in più dell’altezza di
Bk-1. Quindi Bk ha altezza k-1+1 = k;
3) Sia D(k,i) il numero di nodi a livello i in Bk.
Allora
01)0,( kkD
k
kkkkkDkkD 1
1)1,1(),(
1) Bk è costituito da due copie di Bk-1 e quindi
ha 2k-1 + 2k-1 = 2k nodi;
![Page 10: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/10.jpg)
10
Mentre per 0 < i < k i nodi a livello i sono i nodi a livello i di una delle due copie di Bk-1
che formano Bk più i nodi a livello i+1
dell’altra e pertanto
ik
ik
ik
ikDikDikD
111
)1,1(),1(),(
![Page 11: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/11.jpg)
11
4) la radice di Bk ha un figlio più della radice di
Bk-1. Essa ha quindi grado k-1+1 = k;
5) il primo figlio xk-1 della radice di Bk è radice
di uno dei due Bk-1 che lo formano mentre i
figli successivi xk-2, ..., x0 sono i figli dell’altro
Bk-1 e, per ipotesi induttiva, sono quindi radici
di alberi binomiali Bk-2, ..., B0 .
![Page 12: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/12.jpg)
12
Definizione di heap binomiale
1) Ogni albero binomiale di H è ordinato a min-heap: ad ogni nodo è associata una chiave e la chiave di ciascun nodo è maggiore della chiave del padre.
2) Gli alberi binomiali in H hanno gradi distinti.
Def. mucchio binomiale
Un heap binomiale H è un insieme di alberi binomiali tale che:
![Page 13: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/13.jpg)
13
Proprietà degli heap binomiali.Sia H un heap binomiale con n nodi in totale. Allora:
H contiene al più log2 n +1 alberi.
![Page 14: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/14.jpg)
14
Dimostrazione.Sia H un heap binomiale con n nodi in totale e sia bkbk-1...b0 la rappresentazione binaria di n. Allora:
* un albero binomiale Bi in H contiene 2i nodi e quindi n è somma di potenze di 2 distinte. Ma l’unico modo in cui si può esprimere n come somma di potenze di 2 distinte è
k
i
iibn
02
* Il numero di alberi è ≤ al numero di cifre nella rappresentazione binaria di n, ovvero log2 n +1
![Page 15: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/15.jpg)
15
10head[H]
27
38
8 14 29
6
18
2512
1
11 17
I nodi hanno i seguenti campi:key : la chiave;parent : puntatore al padrechild : puntatore al primo figliosibling : puntatore al fratello destrodegree : numero di figli.oltre ad eventuali altri campi per informazioni associate alla chiave
![Page 16: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/16.jpg)
16
sibling
parent
child
head[H] 10 0 1 2
12 1
18 0
25 0 8 2
11 1
27 0
17 0
6 3
14 1
18 0
29 0
![Page 17: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/17.jpg)
17
Link(y, z) PRE: y e z sono radici di alberi binomiali
dello stesso grado
parent[y] z sibling[y] child[z] child[z] y degree[z] degree[z] + 1
Molte operazioni usano la funzione ausiliaria:
Aggiunge y come primo figlio di z. Richiede tempo costante O(1).
Link
![Page 18: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/18.jpg)
18
Minimum(H) PRE: H non è vuoto
x head[H], kmin key[x] while sibling[x] nil do x sibling[x] if kmin > key[x] then kmin key[x] return kmin
La funzione Minimum è:
Siccome ci sono al più log2 n+1 alberi essa richiede tempo O(log n).
Minimum
![Page 19: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/19.jpg)
19
Union(H1,H2) x head[H1], xp nil y head[H2], head[H2] = nil while x nil and y nil do I° while
La funzione Union percorre le due liste delle radici riunendole nella prima delle due.
In dipendenza dei gradi di x e di y si possono presentare i seguenti casi:
Union
![Page 20: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/20.jpg)
20
xxp
y
xxp
y
Caso 1. deg[x] < deg[y]
![Page 21: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/21.jpg)
21
if degree[y] > degree[x] then caso 1
xp x, x sibling[x]
![Page 22: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/22.jpg)
22
Caso 2. deg[y] < deg[x]
xxp
y
xxp
y ys
![Page 23: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/23.jpg)
23
else if degree[y] < degree[x] then caso 2
ys sibling[y] if xp = nil then head[H1] y else sibling[xp] y sibling[y] x, xp y y ys
else caso 3: degree[y] = degree[x]
ys sibling[y]
![Page 24: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/24.jpg)
24
Caso 3.1. key[x] > key[y]
xxp
y
7
4
xxp
y
7
4
ys
![Page 25: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/25.jpg)
25
if key[x] > key[y] then caso 3.1
xs sibling[x] Link(x,y) if xp = nil then head[H1] y else sibling[xp] y sibling[y] xs x y, y ys
else caso 3: degree[y] = degree[x]
ys sibling[y]
![Page 26: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/26.jpg)
26
Caso 3.2. key[y] > key[x]
xxp
y
7
4
xxp
y
4
7
ys
![Page 27: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/27.jpg)
27
else caso 3.2
Link(y,x) y ys
xs sibling[x] while xs nil and degree[x] = degree[xs] do II° while
![Page 28: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/28.jpg)
28
xxp4 7
xs
Caso 3.4.
Caso 3.3.
xxp7 4
xs
xxp
7
4
xs
![Page 29: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/29.jpg)
29
if key[x] > key[xs] then caso 3.3
Link(x,xs) if xp = nil then head[H1] xs else sibling[xp] xs x xs else caso 3.4
sibling[x] sibling[xs] Link(xs,x) xs sibling[x]
![Page 30: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/30.jpg)
30
if y nil then if xp = nil then head[H1] y else sibling[xp] y
![Page 31: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/31.jpg)
31
Siano m1 ed m2 il numero di alberi contenuti nei due heap da unire ed m quello dello heap ottenuto.Il ciclo while più esterno viene eseguito al più m1+m2 volte.
Ad ogni esecuzione del ciclo while interno il numero totale di alberi diminuisce di uno. Quindi esso viene eseguito al più m1 + m2 - m volte.
Siccome m1, m2 ed m sono tutti O(log n) anche Union richiede tempo O(log n).
![Page 32: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/32.jpg)
32
Insert(H, x) parent[x] nil, sibling[x] nil child[x] nil , degree[x] 0 head[H1] x Union(H,H1)
La funzione Insert è:
Siccome Union richiede tempo O(log n) anche Insert richiede tempo O(log n).
Insert
![Page 33: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/33.jpg)
33
10head[H]
27
38
8 14 29
6
18
2512
1
11 17
10head[H]
27
38
8 14 29
6
18
2512
1
11 17
x
ExtractMin
![Page 34: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/34.jpg)
34
10head[H]
27
38
8 14 29
6
18
2512
1
11 17
x
10head[H]
27
38
8 14 29
6
18
25 12
1
11 17
x
head[H1]
![Page 35: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/35.jpg)
35
10head[H]
27
38
8 14 29
6
18
25 12
1
11 17
x
head[H1]
head[H]
27
38
8 14 29
6
18
12
1
11 17
x
25
10
![Page 36: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/36.jpg)
36
ExtractMin(H) x radice con chiave minima - elimina x dalla lista delle radici di H - crea uno heap H’ tale che head[H’] punta alla lista concatenata dei figli di x, invertita Union(H,H1) unisce i due heap
La funzione ExtractMin: idea ExtractMin
![Page 37: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/37.jpg)
37
ExtractMin(H) if head[H] = nil then return nil xp nil y head[H], kmin key[head[H]] while sibling[y] nil do xp radice che precede if kmin > key[sibling[y]] then quella minima
kmin key[sibling[y]], xp y y sibling[y] if xp = nil then la radice minima è la prima
x head[H], head[H] sibling[x] else la radice minima è quella che segue xp
x sibling[xp], sibling[xp] sibling[x]
La funzione ExtractMin è: ExtractMin
![Page 38: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/38.jpg)
38
buildHeap(H1, x) costruisce un heap H1 con i figli di x
Union(H,H1) unisce i due heap
return x
![Page 39: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/39.jpg)
39
buildHeap(H1, x) costruisce un heap H1 con i figli di x
head[H1] nil while child[x] nil do y child[x] child[x] sibling[y] parent[y] nil sibling[y] head[H1] head[H1] y
dove la procedura buildHeap è:
![Page 40: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/40.jpg)
40
buildHeap percorre la lista dei figli di una radice. Siccome il grado è O(log n) anche tale ciclo ha complessità O(log n).
Il primo ciclo while percorre la lista delle radici ed ha quindi complessità O(log n).
Infine Union richiede tempo O(log n) e quindi anche ExtractMin richiede tempo O(log n).
![Page 41: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/41.jpg)
41
DecreaseKey(H, x, k) if k > key[x] then errore “la nuova chiave non è minore della vecchia” key[x] k y parent[x] while y nil and key[y] > key[x] do k key[x], key[x] key[y], key[y] k “scambia anche eventuali campi associati” x y, y parent[x]
La funzione DecreaseKey è:
Siccome l’altezza è O(log n) anche DecreaseKey richiede tempo O(log n).
DecreaseKey
![Page 42: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/42.jpg)
42
Delete(H, x)
DecreaseKey(H, x, -) ExtractMin(H)
La funzione Delete è:
Siccome sia DecreaseKey che ExtractMin hanno complessità O(log n) anche Delete richiede tempo O(log n).
Delete
![Page 43: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/43.jpg)
43
Operazione Complessità Make (1) Insert O(log n) Minimum O(log n) ExtracMin O(log n) Union O(log n) DecreaseKey O(log n) Delete O(log n)
![Page 44: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/44.jpg)
44
Esercizio 26.Supponiamo che non esista una rappresentazione della chiave -. Riscrivere al funzione Delete per gli heap binomiali in modo che essa non usi la chiave -. Assicurarsi che la complessità rimanga O(log n).
![Page 45: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/45.jpg)
45
Esercizio 27.Nella funzione ExtractMin abbiamo dovuto percorrere tutta la lista dei figli del nodo estratto per invertirne l’ordine. Questo perché la lista delle radici è ordinata per grado crescente mentre le liste dei figli sono ordinate per grado decrescente. Cosa succede se ordiniamo le due liste in modo concorde?
![Page 46: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/46.jpg)
46
Operazione Complessità ammortizzata Make (1) Insert (1) Minimum (1) ExtractMin O(log n) Union (1) DecreaseKey (1) Delete O(log n)
Esiste una struttura dati, gli heap di Fibonacci, in cui le stesse operazioni si eseguono con le seguenti complessità ammortizzate.
![Page 47: Mucchi binomiali](https://reader035.vdocumenti.com/reader035/viewer/2022062409/56814881550346895db58eab/html5/thumbnails/47.jpg)
47
Esercizio 28.Dimostrare che non esiste nessuna struttura dati che permetta di eseguire le tre operazioni Make, Insert ed ExtractMin in tempo costante (sia caso pessimo che ammortizzato).