Algoritmi e Strutture Dati
Capitolo 10 - Code con priorità e insiemi disgiunti
Alberto Montresor
Università di Trento
This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License. To view a
copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/2.5/ or send a letter to Creative
Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.
© Alberto Montresor
1
Introduzione
Strutture dati viste finora
✦
Sequenze, insiemi e dizionari
✦
Strutture “speciali”
✦
Le operazioni base (inserimento, cancellazione, lettura, etc.) possono non essere
sufficienti: a volte è necessario inventarsene di nuove
✦
Se non tutte le operazioni sono necessarie, è possibile realizzare strutture dati più
efficienti, “specializzate” per particolare compiti
✦
© Alberto Montresor
2
Code con priorità
L'idea
✦
Una struttura dati – detta heap – che mantiene dati in modo parzialmente ordinato
✦
Utilizzazioni
✦
Code con priorità
✦
Gli oggetti vengono estratti dalla coda in base alla loro priorità
✦
Heapsort
✦
Algoritmo di ordinamento
✦
Costo computazionale: O(n log n)
✦
Ordinamento sul posto
✦
© Alberto Montresor
3
Alberi binari
Albero binario perfetto
✦
Tutte le foglie hanno la stessa profondità h
✦
Nodi interni hanno grado 2
✦
Un albero perfetto
✦
Ha altezza ⎣log N⎦
✦
Altezza h → #nodi= 2h+1-1
✦
Albero binario completo
✦
Tutte le foglie hanno profondità h o h-1
✦
Tutti i nodi a livello h sono “accatastati” a sinistra
✦
Tutti i nodi interni hanno grado 2, eccetto al più uno
✦
© Alberto Montresor
4
Alberi binari heap
Max heap
Un albero binario completo è un
albero max-heap sse
✦
Ad ogni nodo i viene associato
un valore A[i]
16
✦
A[p(i)] ≥ A[i]
✦
Un albero binario completo è un
albero min-heap sse
14
10
✦
8
7
9
3
Ad ogni nodo i viene associato
un valore A[i]
✦
A[p(i)] ≤ A[i]
2 4
1
✦
Le definizioni e gli algoritmi di max-heap sono simmetrici rispetto a min-heap
✦
© Alberto Montresor
5
Alcune informazioni sugli alberi heap
Un albero heap non impone alcuna relazione
di ordinamento fra i figli di un nodo
✦
Un albero heap è un ordinamento parziale
✦
16
14
10
Riflessivo: Ogni nodo è ≥ di se stesso
✦
{a,b}
Antisimmetrico: se n≥m e m≥n, allora m=n
✦
Transitivo: se n≥m e m≥r, allora n≥r
✦
{a}
{b}
Ordinamenti parziali
✦
Utili per modellare gerarchie complesse o
mantenere informazioni parziali
✦
Nozione più debole di un ordinamento totale...
✦
Ma più semplice da costruire
✦
© Alberto Montresor
6
Array heap
E' possibile rappresentare un albero binario heap tramite un
array heap (oltre che tramite puntatori)
✦
A[1]
16
Come è fatto?
✦
Array A[1..n]
✦
A[2]
14
A[3]
10
A[4] A[5]
A[6] A[7]
Come è organizzato?
✦
A[1] contiene la radice
✦
8
p(i) = ⎣i/2⎦
✦
7
9
3
l(i) = 2i
✦
A[8] 2 4 1 A[10]
A[9]
r(i) = 2i+1
✦
n = 10
16 14 10 8 7 9 3 2 4
© Alberto Montresor
1
7
Array heap
Ricapitolando:
✦
Array max-heap: A[i] ≥ A[2i], A[i] ≥ A[2i+1]
✦
Procedure per gestire heap
✦
maxHeapRestore - O(log n)
✦
Un algoritmo che mantiene la proprietà di max-heap
✦
heapBuild - O(n)
✦
Un algoritmo che costruisce un max-heap da zero
✦
heapsort - O(n log n)
✦
Ordina sul posto un array
✦
© Alberto Montresor
www.xkcd.com
8
maxHeapRestore()
Input
✦
Un array A e un indice i
✦
Gli alberi binari con radici l(i) e r(i) sono max-heap
✦
E' possibile che A[i] sia minore di A[l(i)] o A[r(i)]
✦
In altre parole: il sottoalbero con radice i può non essere un
max-heap
✦
Scopo
✦
Ripristinare la proprietà di max-heap sul sottoalbero con radice i
✦
Facendo “scendere” l'elemento A[i] nell'array
✦
© Alberto Montresor
9
maxHeapRestore()
© Alberto Montresor
10
maxHeapRestore()
Domanda: Esempio di funzionamento
✦
5, 15, 12, 9, 10, 7, 4, 3, 6, 8, 2
✦
E' un array max-heap?
✦
E' possibile applicare maxHeapRestore() alla radice?
✦
Domanda:
✦
Qual è la complessità in tempo di maxHeapRestore()?
✦
Domanda
✦
Dimostrare la correttezza di maxHeapRestore()
✦
© Alberto Montresor
11
heapBuild()
Principio generale
✦
Sia A[1..n] un array da ordinare
✦
Tutti i nodi A[⎣n/2⎦+1 ... n] sono foglie dell'albero e quindi heap di un elemento da
cui iniziare
✦
La procedura heapBuild() attraversa i restanti nodi dell'albero ed esegue
maxHeapRestore()
✦
© Alberto Montresor
12
heapBuild()
Domanda: Esempio di funzionamento
✦
14
14, 45, 28, 34, 15, 20, 12, 30, 21, 25, 16, 22
✦
Domanda: Correttezza
✦
Esprimere un'invariante di ciclo
✦
45
28
Dimostrare la sua correttezza
✦
Domanda – Complessità
✦
Qual è la complessità di
heapBuild()?
34
15
20
12
✦
30
© Alberto Montresor
21
25
16
22
13
Complessità
Le operazioni maxHeapRestore() vengono eseguite su heap di altezza variabile
✦
Viene eseguito ⎡n/2⎤ volte su heap di altezza 0
✦
Viene eseguito ⎡n/4⎤ volte su heap di altezza 1
✦
Viene eseguito ⎡n/8⎤ volte su heap di altezza 2
✦
...Viene eseguito ⎡n/2h+1⎤ volte su heap di altezza h
✦
Da cui si deduce
✦
Ricordate:
✦
Per x < 1
✦
© Alberto Montresor
14
Ordinamento tramite heap
Intuizione
✦
Il primo elemento dello heap è sempre il massimo
✦
Andrebbe collocato nell'ultima posizione
✦
L'elemento in ultima posizione? In testa!
✦
Chiama maxHeapRestore() per ripristinare la situazione
✦
© Alberto Montresor
15
heapsort()
Domanda: Esempio di funzionamento
✦
45
14, 45, 28, 34, 15, 20, 12, 30, 21, 25, 16, 22
✦
Domanda: Correttezza
✦
Esprimere un'invariante di ciclo
34
✦
28
Dimostrare la sua correttezza
✦
Domanda: Complessità
✦
30
25
22
12
Qual è la complessità di
heapsort()?
✦
14
© Alberto Montresor
21
15
16
20
16
Esercizi
Esercizio
✦
Dimostrare che uno heap con n nodi ha altezza θ(log n)
✦
Esercizio
✦
Scrivere un'implementazione iterativa di maxHeapRestore()
(in pseudo-codice)
✦
Esercizio
✦
Dimostrare che il tempo di esecuzione nel caso peggiore di
maxHeapRestore() è Ω(log n)
✦
Esercizio
✦
Implementare heapsort() nel vostro linguaggio preferito
✦
© Alberto Montresor
17
Code con priorità
Coda con priorità
✦
Una struttura dati che serve a mantenere un insieme S di
elementi x, ciascuno con un valore associato di priorità
✦
© Alberto Montresor
18
Specifica
© Alberto Montresor
19
Code con priorità

Esempio di utilizzo

Simulatore event-driven

Ad ogni evento è associato un timestamp di esecuzione

Ogni evento può generare nuovi eventi, con timestamp arbitrari


Una coda con min-priorità può essere utilizzata per eseguire gli eventi in ordine
di timestamp
Esempi di organizzazione
p 3 ev
p 7 ev
© Alberto Montresor
evento
p 5 ev
p
p
p
p
p
p
3
4
5
6
8
7
ev
ev
ev
ev
ev
ev
20
Code con priorità
© Alberto Montresor
21
Inserimento
© Alberto Montresor
22
Code con priorità - minHeapRestore()
© Alberto Montresor
23
Rimozione del minimo e riduzione priorità
© Alberto Montresor
24
Code con priorità
Esercizio
✦
Qual è la complessità delle operazioni sulle code con priorità?
✦
Esercizio
✦
Scrivere lo pseudocodice di una versione heapBuild() basata sulla insert()
✦
Le due procedure creano lo stesso heap? Dimostrare o
produrre un esempio contrario
✦
Qual è la complessità di questa versione di heapBuild()?
✦
Esercizio
✦
L'azione di delete(PriorityItem x) cancella l'elemento x dallo heap. Scrivete una
versione di delete() che operi in tempo O(log n).
✦
© Alberto Montresor
25
Struttura dati per insiemi disgiunti
Motivazioni
✦
In alcune applicazioni siamo interessati a gestire insiemi disgiunti
di oggetti
✦
Esempio: componenti di un grafo
✦
Operazioni fondamentali:
✦
unire più insiemi
✦
identificare l'insieme a cui appartiene un oggetto
✦
Struttura dati
✦
Una collezione S = { S1, S2, ..., Sn } di insiemi dinamici disgiunti
✦
Ogni insieme è identificato da un rappresentante univoco
✦
© Alberto Montresor
26
Scelta del rappresentante
Il rappresentante può essere un qualsiasi membro dell’insieme Si
✦
Operazioni di ricerca del rappresentante su uno stesso insieme devono restituire
sempre lo stesso oggetto
✦
Solo in caso di unione con altro insieme il rappresentante può
cambiare
✦
Il rappresentante può essere un elemento specifico dell’insieme
✦
Si devono definire le caratteristiche degli insiemi e una regola
per caratterizzare il rappresentante
✦
Esempio: l’elemento più piccolo/grande di un insieme
✦
© Alberto Montresor
27
Primitive degli insiemi disgiunti (Merge-Find)
© Alberto Montresor
28
Esempio
mfset(6)
1
2
3
4
5
6
merge(1,2)
1 1, 2 2
3
4
5
6
merge(3,4)
1 1, 2 2
3 3,4 4
5
6
merge(5,6)
1 1, 2 2
3 3,4 4
5 5,6 6
merge(1,3)
1
1,
2 2, 3, 34
merge(1,5)
1
2
© Alberto Montresor
4
1, 2,
3 3, 4, 45, 6
5 5,6 6
5
6
29
Esempio: come utilizzare Merge-Find
Determinare le componenti connesse di un grafo non orientato dinamico
✦
Algoritmo
✦
Si inizia con componenti connesse costituite da un unico vertice
✦
L'operazione merge(find(u), find(v)) viene eseguita per ogni arco (u,v)
✦
Alla fine, avremo l'insieme delle componenti connesse
✦
Complessità
✦
Costo: O(n) + m operazioni merge()
✦
Questo algoritmo è interessante per
la capacità di gestire grafi dinamici
(in cui gli archi vengono aggiunti)
✦
© Alberto Montresor
30
Implementazione di Union-Find
Algoritmi elementari:
✦
Realizzazione basata su liste
✦
find():
✦
O(1);
merge():
O(n)
Realizzazione basata su alberi
✦
merge():
✦
O(1);
find():
O(n)
Algoritmi basati su euristiche di bilanciamento
✦
Realizzazione basata su liste + Euristica sul peso
✦
Realizzazione basata su alberi + Euristica sul rango
✦
Algoritmi finale
✦
Alberi + rango + compressione dei percorsi
✦
© Alberto Montresor
31
Realizzazione basata su liste
Ogni insieme viene rappresentato con una lista concatenata
✦
Il primo oggetto di una lista è il rappresentante dell’insieme
✦
Ogni elemento nella lista contiene:
✦
un oggetto
✦
un puntatore all’elemento successivo
✦
un puntatore al rappresentante
✦
#
head
tail
© Alberto Montresor
c
h
e
b
Può essere
visto come
un albero di
altezza 1
32
Realizzazione basata su liste
L’operazione find(x) richiede tempo O(1)
✦
Si restituisce il rappresentante di x
✦
L’operazione merge(x,y) è più complessa:
✦
Si “appende” la lista che contiene y alla lista che contiene x
✦
I puntatori ai rappresentanti della lista “appesa” devono essere modificati
✦
Costo nel caso pessimo per n operazioni: O(n2)
✦
Costo ammortizzato: O(n)
✦
merge(2,1), merge(3,1), merge(4,1), etc.
✦
© Alberto Montresor
33
QuickFind: Esempio - merge(h, g)
c
h
f
© Alberto Montresor
e
g
b
d
z
f
g
d
z
c
h
e
b
34
Realizzazione basata su alberi (foreste)
Implementazione basata su foresta
✦
Si rappresenta ogni insieme tramite un albero radicato
✦
Ogni nodo dell'albero contiene
✦
l'oggetto
✦
un puntatore al padre
✦
f
c
Il rappresentante è la radice dell'albero
✦
La radice ha come padre un puntatore
a se stessa
✦
Nota: generalmente migliore, non più
veloce delle liste nel caso pessimo
✦
© Alberto Montresor
h
b
e
d
g
35
Realizzazione basata su alberi
Operazioni e costo
✦
find(x)
✦Risale la lista dei padri di x fino a trovare la radice e restituisce la radice come
oggetto rappresentante
✦
Costo: O(n) nel caso pessimo
✦
merge(x,y)
✦
Appende l'albero radicato in y ad x
✦
Costo: O(1)
✦
© Alberto Montresor
36
Realizzazione basata su alberi: Esempio – merge(c, f)
f
c
h
b
e
c
d
h
g
b
e
f
d
g
© Alberto Montresor
37
Realizzazione basata su alberi: Esempio – merge(c, f)
f
c
e
d
g
c
e
f
d
g
© Alberto Montresor
38
Considerazioni
Quando usare....
✦
Realizzazione basata su liste?
✦
Quando le merge() sono rare e le find() frequenti
✦
Realizzazione basate su alberi?
✦
Quando le find() sono rare e le merge() frequenti
✦
E' importante sapere che esistono tecniche euristiche che permettono di migliorare
questi risultati:
✦
Fino a operazioni in tempo ammortizzato O(1) per tutte le utilizzazioni pratiche
✦
© Alberto Montresor
39
Realizzazione basata su liste: Euristica peso
Una strategia per diminuire il costo dell’operazione merge():
✦
Memorizzare l’informazione sulla lunghezza della lista
✦
Appendere la lista più corta a quella più lunga
✦
La lunghezza della lista può essere mantenuta in tempo O(1)
✦
4
2
c
© Alberto Montresor
h
e
b
f
g
40
Realizzazione basata su liste: Euristica peso
Una strategia per diminuire il costo dell’operazione merge():
✦
Memorizzare l’informazione sulla lunghezza della lista
✦
Appendere la lista più corta a quella più lunga
✦
La lunghezza della lista può essere mantenuta in tempo O(1)
✦
6
c
© Alberto Montresor
h
e
b
f
g
41
Realizzazione basata su alberi: Euristica sul rango
Ogni nodo mantiene informazioni sul proprio rango
✦
il rango rango[x] di un nodo x è il numero di archi del cammino più lungo fra x e
una foglia sua discendente
✦
rango ≡ altezza del sottoalbero associato al nodo
✦
Unione di due alberi
con rango diverso
✦
+
c
h
e
b
f
d
Unione di due alberi
con rango uguale
✦
=
c
h
b
+
c
e
f
h
d
b
e
f
=
c
d
h
g
b
e
f
d
g
© Alberto Montresor
42
Compressione dei cammini
Compressione dei cammini: idea
✦
Utilizzata durante le operazioni find(x)
✦
L'albero viene modificato in modo che ricerche successive di x possano completare
in O(1)
✦
Esempio: operazione find(f)
✦
b
e
d
b
f
d
e
f
© Alberto Montresor
43
Compressione dei cammini + rango
Quando si utilizzano entrambe le euristiche:
✦
Il rango non è più l'altezza del nodo ...
✦
...ma il limite superiore all'altezza del nodo
✦
In altre parole:
✦
Le operazioni di compressione dei cammini NON riducono il rango
✦
Sarebbe troppo complesso mantenere le informazioni di altezza
corrette
✦
In ogni caso, non è necessario
✦
© Alberto Montresor
44
Realizzazione basata su alberi + rango + compressione dei cammini
© Alberto Montresor
45
Complessità



Valutiamo ora la complessità di:

Liste + Euristica sul peso

Alberi + Euristica sul rango

Alberi + Euristica sul rango + Compressione dei cammini
Alla lavagna!
Ne segue che tutte queste implementazioni (e in particolare l'ultima) sono
ampiamente utilizzabili in pratica
© Alberto Montresor
46