Post on 01-May-2015
transcript
Heap binari e HeapSort
Algoritmo SelectSort
Invariante di ciclo: ad ogni passo
• gli ultimi i elementi del vettore corrente sono gli i elementi massimi del vettore originale
• gli ultimi i elementi del vettore corrente sono ordinati
Inizializzazione: i = 0
Passo: estrarre l’elemento massimo dal vettore [1..n-i] e
scambiarlo con quello in posizione n-i
Condizione di arresto: i = n
SelectSort(n,A)For j = n downto 2 do {estrai il massimo e mettilo in coda}
j_ max = FindMax(A,j)
“scambia A[j_max] e A[j]”
FindMax(A,j)
i_max = 1
For i = 2 to j do
If A[i_max] < A[i] then i_max = i
return i_max
Pseudocodice di SelectSort
ordinatidisordinati
j
SelectSort
Scandisce la sequenza dall’ultimo elemento al primo
Ad ogni iterazione (FindMax)• cerca l’elemento massimo A[j_max] nella sottosequenza
corrente A[1,…,j]
• scambia l’ultimo elemento con quello massimo (facendo uscire l’elemento massimo dalla sequenza e ricompattandola)
n1
j_max
Complessità O(n2) in ogni caso (anche in quello migliore)
Algoritmo di ordinamento stabile (perché?)
L’algoritmo di ordinamento HeapSort
E’ una variante di SelectSort in cui si estrae l’elemento massimo in tempo costante grazie a uno heap
Lo heap è un albero binario quasi completo (struttura), in cui le etichette dei nodi rispettano certe condizioni
Albero binario:
• insieme vuoto (albero vuoto o nullo)
• unione di tre sottoinsiemi disgiunti
– un nodo detto radice
– un albero binario detto sottoalbero sinistro
– un albero binario detto sottoalbero destro
Alberi binari
sottoalbero sinistro
sottoalbero destro
nodo radice
Qualche definizione sugli alberi
• Nodo foglia (o foglia) di un albero è un nodo i cui sottoalberi sono vuoti (non ha figli)
• Nodo interno di un albero è un nodo che ha figli• Percorso dal nodo i al nodo j è la sequenza di archi da
attraversare per raggiungere il nodo j dal nodo i• Grado di un nodo è il numero dei suoi figli• Profondità di un nodo è il numero di archi del percorso
da esso alla radice• Altezza di un albero è la profondità massima dei suoi
nodi
Alberi
Radice
nodi interni nodi foglia
Grado 1
Grado 2
Grado 0
percorso dallaradice al nodo k
k
Profondità 3
Profondità 2
Profondità 1
Profondità 0
Altezza 3
Alberi binari completi (e quasi)
• Albero binario: tutti i nodi hanno grado 2• Albero binario completo:
– tutti i nodi interni hanno grado 2
– tutte le foglie hanno la stessa profondità
• Albero binario quasi completo– tutte le foglie hanno profondità h o h-1
– tutti i nodi interni hanno grado 2, eccetto al più uno
– se esiste un nodo di grado 1+ è a profondità h-1
+ ha solo il figlio sinistro
+ i nodi alla sua destra (se esistono) sono foglie
Alberi binari quasi completi
nodi foglia
profondità h
profondità h-1
profondità 0
nodo di grado 1
Condizione sulla struttura dell’albero
Proprietà di uno heap
Un albero heap è un albero binario quasi completo con etichette sui nodi, tali che per ogni nodo l’etichetta di entrambi i nodi figli non supera quella del padre.
Condizione sull’etichettatura dell’albero
Un esempio di heap
45
34
2530
28
1222
2114 1615 20
La relazione d’ordine è fra padre e figli, non fra i due figli!
Heap e ordinamenti parziali
Uno heap rappresenta un ordinamento parziale, cioè una relazione tra elementi di un insieme
• riflessiva: x è in relazione con se stesso
x R x• antisimmetrica: se x è in relazione con y e y è in
relazione con x, allora x = y
x R y y R x x = y• transitiva: se x è in relazione con y e y è in relazione
con z, allora x è in relazione con z
x R y y R z x R z
Esempi: le relazioni e (NON le relazioni > e < !)
Heap e ordinamenti parziali
Un albero binario di ricerca rappresenta un ordinamento totale: in un ordinamento totale per ogni coppia di elementi x e y vale o x R y o y R x
Un ordinamento parziale è più debole di uno totale: possono esservi coppie di elementi privi di relazione
Gli ordinamenti parziali modellano gerarchie con informazione incompleta o elementi con uguali valori
Uno heap può essere implementato in vari modi; ad es., come un albero a puntatori, oppure come un array
20
Rappresentazione di uno heap come array
45
34
2530
28
1222
2114 1615 20
1
2 3
4 5 6 7
8 9 10 11 12
1 2 3 4 5 6 7 8 9 10 11 12
45 34 28 30 25 22 12 14 21 15 16
Rappresentazione di uno heap come array
• la radice dello heap sta nella prima posizione dell’array
• se un nodo dello heap sta nella posizione i dell’array
– il figlio sinistro sta nella posizione 2i
– il figlio destro sta nella posizione 2i +1
• viceversa, un array A rappresenta uno heap quando
A[i ] A[2i ] e A[i] A[2i+1]
Rappresentazione di uno heap come array45
34
2530
28
1222
2114 1615 20
1
2 3
4 5 6 7
8 9 10 11 12
45 34 28 30 25 22 12 14 21 15 16 201 2 3 4 5 6 7 8 9 10 11 12
Operazioni elementari su uno heap
LeftSubtree(i) {restituisce la radice del sottoalbero sinistro}
return 2i
RightSubtree(i) {restituisce la radice del sottoalbero destro}
return 2i + 1
Father (i) {restituisce il nodo padre di i}
return i/2
Indichiamo con heapsize(A) n la dimensione dello heap
• Heapify(A,i): ripristina la proprietà di heap nel sottoalbero radicato in i, assumendo che valga già per i sottoalberi destro e sinistro di i
• BuildHeap(A): trasforma il generico array A in uno heap
Heapify
Dati due heap H1 e H2 con radici k >1 e k+1
Si possono fondere i due heap in un albero H con radice
in posizione i = k/2
Se l’ elemento v in posizione A[i] non è v A[k] e
v A[k+1], allora H non è uno heap. Per renderlo tale:
si scambia A[i] con la maggiore fra le radici di H1 e H2
si applica Heapify ricorsivamente al sottoalbero selezionato (con la nuova radice v
in posizione A[2i] o A[2i+1])
Algoritmo Heapify
Heapify(A,i)
l = LeftRoot(i)
r = RightRoot(i)
i_max = i
If l heapsize(A) and A[l] > A[i_max] then i_max = l
If r heapsize(A) and A[r] > A[i_max] then i_max = r
If i_max i then
“scambia A[i] e A[i_max]”
Heapify(A,i_max)
Un esempio di applicazione di Heapify
45
14
2534
28
1222
2130 1615 20
1
2 3
4 5 6 7
8 9 10 11 12
i
i_max = iIf l heapsize(A) and A[l] > A[i_max] then i_max = lIf r heapsize(A) and A[r] > A[i_max] then i_max = r
l r
A
34i_max
Un esempio di applicazione di Heapify
45
14
2534
28
1222
2130 1615 20
1
2 3
4 5 6 7
8 9 10 11 12
i
If i_max i then “scambia A[i] e A[i_max]” ...
i_max l r
A34
14
Un esempio di applicazione di Heapify
45
34
2514
28
1222
2130 1615 20
1
2 3
4 5 6 7
8 9 10 11 12
i
If i_max i then “scambia A[i] e A[i_max]” Heapify(A,i_max)
l r
A
Un esempio di applicazione di Heapify
45
34
2514
28
1222
2130 1615 20
1
2 3
4 5 6 7
8 9 10 11 12
i
l r
A
i_max = iIf l heapsize(A) and A[l] > A[i_max] then i_max = lIf r heapsize(A) and A[r] > A[i_max] then i_max = r
i_max
30
Un esempio di applicazione di Heapify
45
34
2514
28
1222
2130 1615 20
1
2 3
4 5 6 7
8 9 10 11 12
i
l r
A
i_max
30
If i_max i then “scambia A[i] e A[i_max]” ...
30
14
Un esempio di applicazione di Heapify
45
34
2530
28
1222
2114 1615 20
1
2 3
4 5 6 7
8 9 10 11 12
i
If i_max i then “scambia A[i] e A[i_max]” Heapify(A,i_max)
A
Un esempio di applicazione di Heapify
45
34
2530
28
1222
2114 1615 20
1
2 3
4 5 6 7
8 9 10 11 12
iA
I test sono falsil > heapsize(A)r > heapsize(A)per cui i_max = i(caso base)
i_max = iIf l heapsize(A) and A[l] > A[i_max] then i_max = lIf r heapsize(A) and A[r] > A[i_max] then i_max = r
Heapify termina!Ora vale la proprietà heap
Heapify(A,i)
l = LeftRoot(i)
r = RightRoot(i)
i_max = i
If l heapsize(A) and A[l] > A[i_max] then i_max = l
If r heapsize(A) and A[r] > A[i_max] then i_max = r
If i_max i then
“scambia A[i] e A[i_max]”
Heapify(A,i_max)
Complessità di Heapify
T(n) = max[O(1),O(1)+T(n’)]
O(1)
O(1)
f(n) = T(n’)
Complessità di Heapify
Ad ogni chiamata ricorsiva, Heapify viene eseguito su un sottoalbero di n’ nodi dell’albero di n nodi
n’ 2/3 n45
34
2530
28
1222
2114 1615
1
2 3
4 5 6 7
8 9 10 11
n’/n è massimo
n’ n’’
Sottoalbero completodi altezza h-1
Sottoalbero completodi altezza h-2
Complessità di Heapify
45
34
2530
28
1222
2114 15
1
2 3
4 5 6 7
8 9 10
n’ n’’
n’/n non è massimo(n’ è più piccolo!)
Complessità di Heapify
45
34
2530
28
1222
2114 1615
1
2 3
4 5 6 7
8 9 10 112012
n’ n’’
n’/n non è massimo(n è più grande!)
Complessità di Heapify
n’ = 2h - 1n’’ = 2h-1 - 1
n = 1 + n’ + n’’ = 32h-1 - 1
45
34
2530
28
1222
2114 1615
1
2 3
4 5 6 7
8 9 10 11
n’ n’’
Sottoalbero completodi altezza h-1
Sottoalbero completodi altezza h-2
n’/n = 2h-1/(3 2h-1 -1) 2/3
T(n) = max[O(1),max(O(1),O(1) + T(n’))]
max[O(1),max(O(1),O(1) + T(2n/ 3))]
T(2n/3) + (1)
T(n) = O (log n)
Sempre nel caso peggiore, T(n) T(n/3) + (1)
T(n) = (log n)
Heapify impiega tempo proporzionale all’altezza dell’albero
T(n) = (log n)
Complessità di Heapify
BuildHeap
Trasforma l’array A in uno heap riordinando i suoi elementi attraverso l’algoritmo Heapify
Heapify richiede che i due sottoalberi di ogni elemento siano già heap, ma gli ultimi n/2 elementi dell’array lo sono già, perché sono foglie, cioè radici di sottoalberi vuoti
Quindi, basta inserire nello heap i primi n/2 elementi, usando Heapify per ripristinare la proprietà heap sui sottoalberi radicati in essi
BuildHeap(A)
For i = length(A)/2 downto 1 do
Heapify(A,i)
Un esempio di applicazione di BuildHeap
14
45
1534
28
1220
2130 1625 22
1
2 3
4 5 6 7
8 9 10 11 12
14 45 28 34 15 20 12 30 21 25 16 221 2 3 4 5 6 7 8 9 10 11 12
BuildHeap(A)
For i = length(A)/2 downto 1 do
Heapify(A,i)
i = 6
20
Un esempio di applicazione di BuildHeap
14
45
1534
28
1220
2130 1625 22
1
2 3
4 5 6 7
8 9 10 11 12
14 45 28 34 15 22 12 30 21 25 16 201 2 3 4 5 6 7 8 9 10 11 12
BuildHeap(A)
For i = length(A)/2 downto 1 do
Heapify(A,i)
2022
20
heap
i = 6
Un esempio di applicazione di BuildHeap
14
45
1534
28
1222
2130 1625 20
1
2 3
4 5 6 7
8 9 10 11 12
14 45 28 34 15 20 12 30 21 25 16 221 2 3 4 5 6 7 8 9 10 11 12
BuildHeap(A)
For i = length(A)/2 downto 1 do
Heapify(A,i)
15
i = 5
Un esempio di applicazione di BuildHeap
14
45
1534
28
1222
2130 1625 20
1
2 3
4 5 6 7
8 9 10 11 12
14 45 28 34 25 20 12 30 21 15 16 221 2 3 4 5 6 7 8 9 10 11 12
BuildHeap(A)
For i = length(A)/2 downto 1 do
Heapify(A,i)
15
i = 5
25
15
heap
i = 5
Un esempio di applicazione di BuildHeap
14
45
2534
28
1222
2130 1615 20
1
2 3
4 5 6 7
8 9 10 11 12
14 45 28 34 15 20 12 30 21 25 16 221 2 3 4 5 6 7 8 9 10 11 12
BuildHeap(A)
For i = length(A)/2 downto 1 do
Heapify(A,i)
34
heap
i = 4
Un esempio di applicazione di BuildHeap
14
45
2534
28
1222
2130 1615 20
1
2 3
4 5 6 7
8 9 10 11 12
14 45 28 34 15 20 12 30 21 25 16 221 2 3 4 5 6 7 8 9 10 11 12
BuildHeap(A)
For i = length(A)/2 downto 1 do
Heapify(A,i)
heap 28
i = 3
Un esempio di applicazione di BuildHeap
14
45
2534
28
1222
2130 1615 20
1
2 3
4 5 6 7
8 9 10 11 12
14 45 28 34 15 20 12 30 21 25 16 221 2 3 4 5 6 7 8 9 10 11 12
BuildHeap(A)
For i = length(A)/2 downto 1 do
Heapify(A,i)
45 heap
i = 2
Un esempio di applicazione di BuildHeap
14
45
2534
28
1222
2130 1615 20
1
2 3
4 5 6 7
8 9 10 11 12
14 45 28 34 15 20 12 30 21 25 16 221 2 3 4 5 6 7 8 9 10 11 12
BuildHeap(A)
For i = length(A)/2 downto 1 do
Heapify(A,i)
14
i = 1
Un esempio di applicazione di BuildHeap
14
45
2534
28
1222
2130 1615 20
1
2 3
4 5 6 7
8 9 10 11 12
45 14 28 34 15 20 12 30 21 25 16 221 2 3 4 5 6 7 8 9 10 11 12
BuildHeap(A)
For i = length(A)/2 downto 1 do
Heapify(A,i)
14
14
45
i = 1
Un esempio di applicazione di BuildHeap
14
2534
28
1222
2130 1615 20
1
2 3
4 5 6 7
8 9 10 11 12
45 34 28 14 15 20 12 30 21 25 16 221 2 3 4 5 6 7 8 9 10 11 12
BuildHeap(A)
For i = length(A)/2 downto 1 do
Heapify(A,i)
1445
34
14
i = 1
Un esempio di applicazione di BuildHeap
14
25
28
1222
2130 1615 20
1
2 3
4 5 6 7
8 9 10 11 12
45 34 28 30 15 20 12 14 21 25 16 221 2 3 4 5 6 7 8 9 10 11 12
BuildHeap(A)
For i = length(A)/2 downto 1 do
Heapify(A,i)
1445
34
30
14
i = 1
Un esempio di applicazione di BuildHeap
14
25
28
1222
21 1615 20
1
2 3
4 5 6 7
8 9 10 11 12
45 34 28 30 15 20 12 14 21 25 16 221 2 3 4 5 6 7 8 9 10 11 12
BuildHeap(A)
For i = length(A)/2 downto 1 do
Heapify(A,i)
1445
34
30
14
heap
i = 1
Complessità di BuildHeap
BuildHeap chiama n/2 volte Heapify
E’ allora TBH(n) = n/2 TH(n) = O(n log n)?
Sì, ma si può stringere la stima sino a TBH(n) = O(n)
Costruire uno heap di n elementi costa solo O(n)!
Complessità di BuildHeapBuildHeap chiama Heapify • (n/2 volte su heap di altezza 0) (inutile eseguire)
• n/4 volte su heap di altezza 1• n/8 volte su heap di altezza 2• … • n/2h+1 volte su heap di altezza h
14
45
1534
28
1220
2130 1625 22
1
2 3
4 5 6 7
8 9 10 11 12
Complessità di BuildHeap
)(
2)(
log
11
hOn
nfn
hh
n
hh
hnO
log
1 22
0 22 hh
hnO
20 )1( x
xhx
h
h
Poiché )()2/11(
2/1
2)(
2nO
nOnf
Poiché TH = O(log n) e nh log
,
HeapSort
HeapSort è una variante di SelectSort che mantiene la sequenza in uno heap, facilitando così cui la ricerca dell’elemento massimo
• si costruisce uno heap a partire dall’array non ordinato A
• si scandisce l’array a partire dall’ultimo elemento e ad ogni passo
• la radice A[1] (che è l’elemento massimo) viene scambiata con l’ultimo elemento dello heap corrente
• si riduce di uno la dimensione corrente dello heap
• si ripristina la proprietà heap con Heapify
HeapSort e SelectSort
HeapSort(A)
BuildHeap(A)
For j = n downto 2 do { heapsize(A) = j }
“scambia A[1] e A[j]” { j_ max = 1 }
Heapify(A[1,…,j-1],1) { ripristina lo heap, ridotto}
SelectSort(n,A)
For j = n downto 2 do
j_ max = FindMax(A,j)
“scambia A[j_max] e A[j]”
Intuizioni su HeapSort
n1disordinati
parzialmente ordinatiheap
n1
costruisci heapmax
scambio +
Heapifyn1
max
ordinatiparzialmente ordinatiheap
i
Un esempio di esecuzione di HeapSort
HeapSort(A)
BuildHeap(A)
…
14
45
1534
28
1220
2130 1625 22
2 3
4 5 6 7
8 9 10 11 12
34
2530 22
14 15 20
145
Un esempio di esecuzione di HeapSort
HeapSort(A)
…
For j = n downto 2 do “scambia A[1] e A[j]”Heapify(A[1,…,j-1],1) 14
45
1534
28
1220
2130 1625 22
1
2 3
4 5 6 7
8 9 12
34
2530
28
1222
2114 1615 20
45
45
20
j = 12
10 11
Un esempio di esecuzione di HeapSort
HeapSort(A)
…
For j = n downto 2 do “scambia A[1] e A[j]”Heapify(A[1,…,j-1],1) 14
45
1534
28
1220
2130 1625
2 3
4 5 6 7
8 9 10 11
34
2530
28
1222
2114 161512
1
45
45
20
j = 12
Un esempio di esecuzione di HeapSort
HeapSort(A)
…
For j = n downto 2 do “scambia A[1] e A[j]”Heapify(A[1,…,j-1],1) 14
45
1534
28
1220
2130 1625
2 3
4 5 6 7
8 9 10 11
34
2530
28
1222
2114 161512
1
45
45
20
j = 12
30
21
20
34
Un esempio di esecuzione di HeapSort
HeapSort(A)
…
For j = n downto 2 do “scambia A[1] e A[j]”Heapify(A[1,…,j-1],1) 14
15
28
1220
30 1625
2 3
4 5 6 7
8 9 10 11
25
28
1222
14 161512
1
45
45
20
j = 11
30
21
20
34
34
16
Un esempio di esecuzione di HeapSort
HeapSort(A)
…
For j = n downto 2 do “scambia A[1] e A[j]”Heapify(A[1,…,j-1],1) 14
15
28
1220
30 25
2 3
4 5 6 7
8 9 10 11
25
28
1222
14 1512
1
45
45
20
j = 11
30
21
20
34
34
16
Un esempio di esecuzione di HeapSort
HeapSort(A)
…
For j = n downto 2 do “scambia A[1] e A[j]”Heapify(A[1,…,j-1],1) 14
15
28
1220
30 25
2 3
4 5 6 7
8 9 10 11
25
28
1222
14 1512
1
45
45
20
j = 11
30
21
20
34
34
16
25
16
30
Un esempio di esecuzione di HeapSort
HeapSort(A)
…
For j = n downto 2 do “scambia A[1] e A[j]”Heapify(A[1,…,j-1],1)
28
1220
30 15
2 3
4 5 6 7
8 9 10 11
28
1222
1412
1
j = 10
21
20 34
25
16
30
30
15
45
Un esempio di esecuzione di HeapSort
HeapSort(A)
…
For j = n downto 2 do “scambia A[1] e A[j]”Heapify(A[1,…,j-1],1)
28
1220
30
2 3
4 5 6 7
8 9 10 11
28
1222
1412
1
j = 10
21
20 34
25
16
30
30
15
45
Un esempio di esecuzione di HeapSort
HeapSort(A)
…
For j = n downto 2 do “scambia A[1] e A[j]”Heapify(A[1,…,j-1],1)
28
1220
30
2 3
4 5 6 7
8 9 10 11
28
1222
1412
1
j = 10
21
20 34
25
16
30
30
15
45
22
15
28
Un esempio di esecuzione di HeapSort
HeapSort(A)
…
For j = n downto 2 do “scambia A[1] e A[j]”Heapify(A[1,…,j-1],1)
28
1220
30
2 3
4 5 6 7
8 9 10 11
22
1215
1412
1
j = 9
21
20 34
25
16
30
30
28
45
20
28
Un esempio di esecuzione di HeapSort
HeapSort(A)
…
For j = n downto 2 do “scambia A[1] e A[j]”Heapify(A[1,…,j-1],1)
28
1220
30
2 3
4 5 6 7
8 9 10 11
22
1215
1412
1
j = 9
21
34
25
16
30 45
20
28
Un esempio di esecuzione di HeapSort
HeapSort(A)
…
For j = n downto 2 do “scambia A[1] e A[j]”Heapify(A[1,…,j-1],1)
28
1220
30
2 3
4 5 6 7
8 9 10 11
22
1215
1412
1
j = 9
21
34
25
16
30 45
20
28
20
21
25
Un esempio di esecuzione di HeapSort
HeapSort(A)
…
For j = n downto 2 do “scambia A[1] e A[j]”Heapify(A[1,…,j-1],1)
28
1220
30
2 3
4 5 6 7
8 9 10 11
22
1215
1412
1
j = 8
34
16
30 4528
20
21
25
25
14
Un esempio di esecuzione di HeapSort
HeapSort(A)
…
For j = n downto 2 do “scambia A[1] e A[j]”Heapify(A[1,…,j-1],1)
28
1220
2 3
4 5 6 7
8 9 10 11
22
1215
12
1
j = 8
34
16
30 4528
20
21
25
25
14
Un esempio di esecuzione di HeapSort
HeapSort(A)
…
For j = n downto 2 do “scambia A[1] e A[j]”Heapify(A[1,…,j-1],1)
28
1220
2 3
4 5 6 7
8 9 10 11
22
1215
12
1
j = 8
34
16
30 4528
20
21
25
25
14
15
14
22
Un esempio di esecuzione di HeapSort
HeapSort(A)
…
For j = n downto 2 do “scambia A[1] e A[j]”Heapify(A[1,…,j-1],1)
12
2 3
4 5 6 7
8 9 10 11
12
12
1
j = 7
34
16
30 4528
20
21
25
15
14
22
22
12
Un esempio di esecuzione di HeapSort
HeapSort(A)
…
For j = n downto 2 do “scambia A[1] e A[j]”Heapify(A[1,…,j-1],1)
2 3
4 5 6
7 8 9 10 11 12
1
j = 7
34
16
30 4528
20
21
25
15
14
12
22
Un esempio di esecuzione di HeapSort
HeapSort(A)
…
For j = n downto 2 do “scambia A[1] e A[j]”Heapify(A[1,…,j-1],1)
2 3
4 5 6
7 8 9 10 11 12
1
j = 7
34
16
30 4528
20
21
25
15
14
12
22
12
20
21
Un esempio di esecuzione di HeapSort
HeapSort(A)
…
For j = n downto 2 do “scambia A[1] e A[j]”Heapify(A[1,…,j-1],1)
2 3
4 5 6
7 8 9 10 11 12
1
j = 6
34
16
30 4528
20
20
25
15
14
22
12
21
21
14
Un esempio di esecuzione di HeapSort
HeapSort(A)
…
For j = n downto 2 do “scambia A[1] e A[j]”Heapify(A[1,…,j-1],1)
2 3
4 5
6 7 8 9 10 11 12
1
j = 6
34
16
30 4528
20
25
15
22
12
21
21
14
Un esempio di esecuzione di HeapSort
HeapSort(A)
…
For j = n downto 2 do “scambia A[1] e A[j]”Heapify(A[1,…,j-1],1)
2 3
4 5
6 7 8 9 10 11 12
1
j = 6
34
16
30 4528
20
25
15
22
12
21
21
14
14
16
20
Un esempio di esecuzione di HeapSort
HeapSort(A)
…
For j = n downto 2 do “scambia A[1] e A[j]”Heapify(A[1,…,j-1],1)
2 3
4 5
6 7 8 9 10 11 12
1
j = 5
3430 452825
15
22
12
21
14
16
20
20
14
Un esempio di esecuzione di HeapSort
HeapSort(A)
…
For j = n downto 2 do “scambia A[1] e A[j]”Heapify(A[1,…,j-1],1)
2 3
4
5 6 7 8 9 10 11 12
1
j = 5
3430 452825
15
22
12
21
16
20
20
14
Un esempio di esecuzione di HeapSort
HeapSort(A)
…
For j = n downto 2 do “scambia A[1] e A[j]”Heapify(A[1,…,j-1],1)
2 3
4
5 6 7 8 9 10 11 12
1
j = 5
3430 452825
15
22
12
21
16
20
20
14
14
16
Un esempio di esecuzione di HeapSort
HeapSort(A)
…
For j = n downto 2 do “scambia A[1] e A[j]”Heapify(A[1,…,j-1],1)
2 3
4
5 6 7 8 9 10 11 12
1
j = 4
3430 452825
15
22
12
2120
14
16
16
12
Un esempio di esecuzione di HeapSort
HeapSort(A)
…
For j = n downto 2 do “scambia A[1] e A[j]”Heapify(A[1,…,j-1],1)
2 3
4 5 6 7 8 9 10 11 12
1
j = 4
3430 452825
15
222120
14
16
16
12
Un esempio di esecuzione di HeapSort
HeapSort(A)
…
For j = n downto 2 do “scambia A[1] e A[j]”Heapify(A[1,…,j-1],1)
2 3
4 5 6 7 8 9 10 11 12
1
j = 4
3430 452825
15
222120
14
16
16
12
12
15
Un esempio di esecuzione di HeapSort
HeapSort(A)
…
For j = n downto 2 do “scambia A[1] e A[j]”Heapify(A[1,…,j-1],1)
2 3
4 5 6 7 8 9 10 11 12
1
j = 3
3430 452825222120
14
16
12
15
15
12
Un esempio di esecuzione di HeapSort
HeapSort(A)
…
For j = n downto 2 do “scambia A[1] e A[j]”Heapify(A[1,…,j-1],1)
2
3 4 5 6 7 8 9 10 11 12
1
j = 3
3430 452825222120
14
16
15
15
12
Un esempio di esecuzione di HeapSort
HeapSort(A)
…
For j = n downto 2 do “scambia A[1] e A[j]”Heapify(A[1,…,j-1],1)
2
3 4 5 6 7 8 9 10 11 12
1
j = 3
3430 452825222120
14
16
15
15
12
12
14
Un esempio di esecuzione di HeapSort
HeapSort(A)
…
For j = n downto 2 do “scambia A[1] e A[j]”Heapify(A[1,…,j-1],1)
2
3 4 5 6 7 8 9 10 11 12
1
j = 2
3430 4528252221201615
12
14
14
12
Un esempio di esecuzione di HeapSort
HeapSort(A)
…
For j = n downto 2 do “scambia A[1] e A[j]”Heapify(A[1,…,j-1],1)
2 3 4 5 6 7 8 9 10 11 12
1
j = 2
3430 4528252221201615
12
14
12
Un esempio di esecuzione di HeapSort
HeapSort(A)
…
For j = n downto 2 do “scambia A[1] e A[j]”Heapify(A[1,…,j-1],1)
2 3 4 5 6 7 8 9 10 11 121
j = 2
3430 45282522212016151412
L’array A ora è ordinato!
Invariante di ciclo per HeapSort
Invariante di ciclo: ad ogni passo
• gli ultimi i elementi del vettore corrente sono gli i elementi massimi del vettore originale
• gli ultimi i elementi del vettore corrente sono ordinati
• i primi n-i elementi del vettore corrente formano uno heap
Inizializzazione: i = 0 e BuildHeap()
Passo: estrarre l’elemento massimo dal vettore [1..n-i] e
scambiarlo con quello in posizione n-i e recuperare la
proprietà heap nel vettore [1..n-i-1]
Condizione di arresto: i = n
Complessità di HeapSort
)(log nO
)(1O
HeapSort(A)
BuildHeap(A)
For j = n downto 2 do “scambia A[1] e A[j]”Heapify(A[1,…,j-1],1)
)(nO
Nel caso peggiore HeapSort chiama • 1 volta BuildHeap• n-1 volte Heapify sullo heap corrente
THS(n) = max[O(n), (n-1) max(O(1), TH(n))]= max[O(n), max(O(n), O(n log n))] = O(n log n)
Conclusioni su HeapSort
• E’ un algoritmo di ordinamento sul posto per confronto e impiega tempo O(n log n)
• Non è un algoritmo elementare• Sfrutta le proprietà della struttura dati astratta heap.• Dimostra che una buona rappresentazione dei dati
spesso facilita il progetto di buoni algoritmi