Per valutare la complessità ammortizzata scomponiamo ogni Union:

nelle due FindSet e nella Link che la costituiscono e valuteremo la complessità in funzione del numero m di operazioni MakeSet, FindSet e Link così ottenute.

Union(x, y) x = FindSet(x) y = FindSet(y) Link(x, y)

Se m' è il numero di operazioni MakeSet, FindSet e Union della sequenza originale allora m' m 3m'

Quindi possiamo calcolare la complessità asintotica in funzione di m invece che di m'.

Useremo il metodo del potenziale. Per definire la funzione potenziale ci servono alcune premesse.

MakeSet(x) x.p = x x.rank = 0

FindSet(x) if x.p x x.p = FindSet(x.p) return x.p

Link(x, y) if x.rank > y.rank y.p = x else x.p = y if x.rank == y.rank y.rank = y.rank + 1

Proprietà dei ranghi

Per ogni nodo x

a) x viene creato come radice con x.rank = 0

b) x.rank aumenta soltanto finché x resta radice, dopo di che rimane invariato.

c) Se x non è radice x.rank < x.p.rank

d) x.p.rank può solo aumentare.

e) dopo aver eseguito n operazioni x.rank < n

Le due funzioni level(x) e iter(x)

).(..: max)( rankxArankpxkxlevel k

).(..: max)( )()( rankxArankpxixiter i

xlevel

Valgono le seguenti diseguaglianze

)()(0 nxlevel

rankxxiter .)(1

Per ogni nodo x non radice definiamo due funzioni che “misurano” la differenza di rango tra x e x.p.

Dimostrazione:

0)(

).(1... 0

xlevel

rankxArankxrankpx

)()(

..)1().( )()(

nxlevel

rankpxnArankxA nn

1)(

).().(.. )1()()(

xiter

rankxArankxArankpx xlevelxlevel

rankxxiter

rankpxrankxArankxA xlevelrankx

xlevel

.)(

..).().( 1)()1.(

)(

Ad ogni nodo x attribuiamo un potenziale (o credito)

rankxnx .)()(0 (x) soddisfa le diseguaglianze

altrimenti )(.)()(

0. oppure radice è se .)()(

xiterrankxxleveln

rankxxrankxnx

Nel primo caso rankxnx .)()(0

rankxnrankxn

xiterrankxxlevelnx

.)(1.)0)((

)(.))()(()(

Nel secondo caso

0)(.1

)(.))()(()(

xiterrankx

xiterrankxxlevelnx

x

x)(

Definiamo un potenziale globale come somma dei potenziali di tutti i nodi

Valutiamo la differenza di potenziale dovuta alla i-esima operazione:

x x iiiii xx )()( 11

Se la i-esima operazione è una MakeSet(x) il potenziale del nodo x è 0 mentre il potenziale degli altri nodi rimane invariato. Quindi

0 i

Dimostriamo che se x non è radice il potenziale di x non può aumentare, ossia

0)( xi

Ed inoltre che se x.rank 1 e la i-esima operazione modifica o level(x) o iter(x) il potenziale diminuisce

1)( xi

Supponiamo quindi che la i-esima operazione sia una Link o FindSet.

Dimostrazione:Se x non è radice x.rank non cambia. Inoltre Link e FindSet non cambiano n e quindi anche (n) non cambia.

Se x.rank = 0 0)( xi

Supponiamo x.rank 1. 0)( xiSe level(x) e iter(x) non cambiano

Se level(x) non cambia ma cambia iter(x) allora iter(x) può solo crescere e quindi

1)( xi

Se level(x) cambia, iter(x) può anche diminuire ma, per i limiti visti, un aumento di level(x) diminuisce (x) di almeno x.rank mentre una diminuzione di iter(x) aumenta (x) al più di x.rank-1. Anche in questo caso 1)( xi

Calcoliamo il costo ammortizzato delle tre operazioni

MakeSet(x) x.p = x x.rank = 0

FindSet(x) if x.p x x.p = FindSet(x.p) return x.p

Link(x, y) if x.rank > y.rank y.p = x else x.p = y if x.rank == y.rank y.rank = y.rank + 1

Costo ammortizzato di MakeSet(x)

0 i

)1(1ˆ Occ i

Costo ammortizzato di Link(x,y)

Il potenziale (x) dipende soltanto da x.rank e x.p.rank. Quindi gli unici elementi il cui potenziale può cambiare sono x, y e i figli di y.

I figli di y non sono radici e il loro potenziale non può aumentare.

x è radice e diventa figlio di y ma il suo rango non cambia.

0)(.)(

.)()(

.))()(()(

xiterrankxxlevel

rankxnxiter

rankxxlevelnxi

Altrimenti

Se x.rank = 0

0.)(.)()( rankxnrankxnxi

y rimane radice e y.rank o rimane invariato o aumenta di 1. Quindi

)(.)(.)()( 1 nrankynrankyny iii

)(ni

))(()(1ˆ nOncc i

Dunque

ed il costo ammortizzato di Link è

Costo ammortizzato di FindSet(x)Il costo reale è proporzionale al numero s di nodi del cammino percorso. Il potenziale della radice non cambia mentre i potenziali degli altri nodi possono solo diminuire.

Consideriamo dapprima come cambia il potenziale dei nodi x del cammino che hanno x.rank > 0 e che sono seguiti da almeno un nodo y diverso dalla radice e tale che level(y) = level(x).

).()).((

)..().(..)1)(())(( rankxArankxAA

rankpxArankyArankpyxiter

kxiter

kk

kk

Sia k = level(y) = level(x). Allora

dopo la compressione

).(.... )1)(( rankxArankpyrankpx xiterk

Dunque iter(x) aumenta di almeno 1 e quindi

1)( xi

I nodi rimanenti sono la radice, il primo nodo se ha rango 0 e per ogni livello k l’ultimo nodo del cammino avente level(x) = k.Siccome i livelli distinti sono al più (n) ci sono al più (n)+2 nodi il cui potenziale può rimanere invariato mentre il potenziale degli altri s-(n)-2 diminuisce di almeno 1. Quindi

2)( nsi

))((2)(ˆ nOnsscc i

ed il costo ammortizzato di FindSet è

Esercizio 31 . (Problema 22-3 del libro.)In un albero T il minimo antenato comune di due nodi u e v è il nodo w a profondità massima che è antenato sia di u che di v.

uv

w

Nel problema dei minimi comuni antenati off-line sono dati un albero T con n nodi ed una lista

L = (u1,v1), ... ,(um,vm)

di m coppie di nodi

Si chiede di calcolare la lista

W = w1, ... ,wm

dei minimi comuni antenati di ogni coppia.

L’algoritmo di Tarjan risolve il problema in tempo lineare O(n+m) con una sola percorrenza dell’albero.

I nodi dell’albero hanno i seguenti campi:

- child : punta al primo figlio

- sibling : punta al fratello

- ancestor : punta ad un antenato- color : white all’inizio e poi diventa black.

oltre ai campi p e rank per insiemi disgiunti.

MinComAnt(u) MakeSet(u) u.ancestor = u v = u.child while v ≠ nil // percorre la lista dei figli MinComAnt(v) Union(u,v) FindSet(u).ancestor = u v = v.sibling u.color = black for “ogni v tale che (u,v) ≡ (ui ,vi) L” if v.color == black wi = FindSet(v).ancestor

L’algoritmo di Tarjan:

x0

x1

x2

......

r0

r1

rk-1

S0

S1

S2

Sk-1xk-1

r2

ri = rappresentanteMinComAnt(u) x0 = root, xk = u

xk

Esercizio 30 . (Problema 22-1 del libro)Sia dato l’insieme T = {1, 2, ... , n} ed una sequenza S = {o1 , o2 , ... , on+m } di n+m operazioni delle quali n sono Insert che inseriscono gli elementi di T una e una sola volta ed m sono ExtractMin che estraggono il minimo tra gli elementi inseriti e non ancora estratti. Supponiamo che ogni ExtractMin della sequenza sia preceduta da più Insert che ExtractMin.

Una possibile sequenza con n = 9 ed m = 6 è:

In cui le Insert sono indicate con i valori 1, 2,..., n inseriti mentre le ExtractMin sono indicate con Ej per j = 1,…, m.

S = { 4, 8, E1, 3, E2, 9, 2, 6, E3, E4, E5, 1, 7, E6, 5 }

Si chiede un algoritmo efficiente che data la sequenza S di operazioni calcoli la sequenza X = {x1, x2, ..., xm} degli m elementi estratti.

Il risultato dovrebbe essere

Ad esempio, con

X = {4, 3, 2, 6, 8, 1}

S = { 4, 8, E1, 3, E2, 9, 2, 6, E3, E4, E5, 1, 7, E6, 5 }

Soluzione.

Per ogni valore i = 1,…,n calcoliamo l’indice j dell’operazione ExtractMin che lo estrae e poniamo Xj = i.

Se i non viene estratto poniamo j = m+1 e non memorizziamo i in X.

S ={4, 8, E1, 3, E2, 9, 2, 6, E3, E4, E5, 1, 7, E6, 5, C7}

Consideriamo la sequenza dell’esempio in cui abbiamo aggiunto alla fine un contenitore C7 a cui associare i valori non estratti.

L’elemento 1 viene estratto da E6.

Poniamo quindi X6 = 1 e a questo punto l’estrazione E6 è stata effettuata.

L’elemento 2 viene estratto da E3. Quindi X3 = 2

S ={4, 8, E1, 3, E2, 9, 2, 6, E3, E4, E5, 1, 7, E6, 5, C7}X ={#, #, 2, #, #, 1}

S ={4, 8, E1, 3, E2, 9, 2, 6, E3, E4, E5, 1, 7, E6, 5, C7}

X ={#, #, #, #, #, 1}

La situazione è:

L’elemento 3 viene estratto da E2. Quindi X2 = 3

S ={4, 8, E1, 3, E2, 9, 2, 6, E3, E4, E5, 1, 7, E6, 5, C7}X ={#, 3, 2, #, #, 1}L’elemento 4 viene estratto da E1. Quindi X1 = 4

L’elemento 5 non viene estratto e rimane associato a C7. Noi infatti manteniamo associato ogni valore alla ExtractMin successiva non ancora effettuata o a C7 se non ce ne sono altre.

L’elemento 6 è associato ad E4 e quindi X4 = 6.

S ={4, 8, E1, 3, E2, 9, 2, 6, E3, E4, E5, 1, 7, E6, 5, C7}X ={4, 3, 2, #, #, 1}

La situazione è

L’elemento 7 è associato a C7 e viene scartato.

L’elemento 9 è associato a C7 e viene scartato.

Il risultato è quindi X = {4, 3, 2, 6, 8, 1}

S ={4, 8, E1, 3, E2, 9, 2, 6, E3, E4, E5, 1, 7, E6, 5, C7}X ={4, 3, 2, 6, #, 1}

L’elemento 8 è associato ad E5 e quindi X5 = 8.

S ={4, 8, E1, 3, E2, 9, 2, 6, E3, E4, E5, 1, 7, E6, 5, C7}X ={4, 3, 2, 6, 8, 1}

La situazione è

Implementazione.Usiamo una struttura dati per insiemi disgiunti.

Manteniamo raggruppati in un insieme Ij gli elementi associati ad ogni Ej non ancora effettuata e in un insieme Im+1 quelli associati a Cm+1.

Su questi insiemi vogliamo eseguire in tempo costante le operazioni MakeSet(i), Union(i,h), FindSet(i) ed inoltre FindIndex(i) che calcola l’indice j della Ej non effettuata (o l’indice m+1 di Cm+1) a cui l’elemento i risulta associato.

Le prime tre sono quelle standard e per poter eseguire la FindIndex(i) basta memorizzare nel rappresentante di ogni insieme l’indice j della Ej non effettuata (o l’indice m+1 di Cm+1) a cui l’insieme è associato.

Rimane un problema: qualcuno degli insiemi può essere vuoto mentre la struttura dati per insiemi disgiunti richiede che essi siano tutti non vuoti.

All’inizio creiamo quindi m+1 insiemi I1 ,…,Im+1 dove Ij = {n+j} contiene soltanto l’elemento fittizio e memorizziamo l’indice j nell’unico nodo.Tempo O(m).

Per ovviare a questo aggiungiamo ad ogni insieme Ij un elemento fittizio di valore i = n+j.

Percorriamo quindi la sequenza delle operazioni e, finché non troviamo la prima ExtractMin, aggiungiamo gli elementi inseriti all’insieme I1.

Dopo di che gli elementi inseriti prima della seconda ExtractMin vengono aggiunti a I2 e così via fino ad aggiungere ad Im+1 tutti gli elementi inseriti dopo l’ultima ExtractMin.

Tempo O(n+m).

Per aggiungere un nuovo elemento i ad un insieme Ij dobbiamo usare la MakeSet(i) e poi usare la Union(i, m+j) per riunire i due insiemi (ricordiamo che m+j è l’elemento fittizio di Ij ).

Naturalmente se l’unione cambia il rappresentante occorre ricordarsi di memorizzare l’indice j dell’insieme nel nuovo rappresentante.

Quando il nostro algoritmo decide che l’elemento i viene estratto da Ej dobbiamo porre

X[j] = i

A questo punto, siccome Ej è stata eseguita, gli elementi dell’insieme Ij a cui appartiene i devono essere associati alla successiva ExtractMin Ek non ancora eseguita o a Cm+1 se tutte le ExtractMin successive sono state eseguite.

Dobbiamo però prima trovare h. Per fare questo manteniamo i rappresentanti degli insiemi Ij in una lista doppiamente concatenata e ordinata rispetto all’indice j.

Occorre quindi effettuare una Union(i,h) dove h è un elemento di Ik associato ad Ek o di Im+1 associato a Cm+1.

Supponiamo di aver elaborato gli elementi 1,…,i-1.

Per trovare l’indice j della ExtractMin non saturata che estrae i basta calcolare j = FindIndex(i).

Se j = m+1 l’elemento i è stato inserito dopo l’ultima ExtractMin non saturata e quindi non viene estratto.Altrimenti esso è estratto da Ej e possiamo porre

X[j] = i.

Tutto questo richiede un tempo costante per ciascun elemento e quindi tempo O(n) in totale.