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
Pseudocodice di SelectSort
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
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)
j_max
j
n
1
disordinati
ordinati
Algoritmo di ordinamento stabile (perché?)
Complessità O(n2) in ogni caso (anche in quello migliore)
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
nodo radice
sottoalbero destro
sottoalbero sinistro
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
percorso dalla
radice al nodo k
Profondità 1
Profondità 0
Grado 2
Profondità 2
Grado 1
Profondità 3
Grado 0
k
nodi interni
nodi foglia
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
profondità 0
nodo di grado 1
profondità h-1
profondità h
nodi foglia
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 sulla struttura dell’albero
Condizione sull’etichettatura dell’albero
Un esempio di heap
45
34
28
30
14
25
21
15
22
16
12
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
xRx
• antisimmetrica: se x è in relazione con y e y è in
relazione con x, allora x = y
xRyyRxx=y
• transitiva: se x è in relazione con y e y è in relazione
con z, allora x è in relazione con z
xRyyRzxRz
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
Rappresentazione di uno heap come array
45
1
34
28
2
3
30
25
22
12
4
5
6
7
14
21
15
16
20
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 20
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 array
45
1
34
28
2
3
30
25
22
12
4
5
6
7
14
21
15
16
20
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 20
Operazioni elementari su uno heap
LeftSubtree(i)
return 2i
{restituisce la radice del sottoalbero sinistro}
RightSubtree(i)
return 2i + 1
{restituisce la radice del sottoalbero destro}
Father (i)
return i/2
{restituisce il nodo padre di i}
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
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
45
1
A
i 14
2
28
3
i_max 34 l
4
25 r
5
30
21
15
16
20
8
9
10
11
12
22
12
6
7
Un esempio di applicazione di Heapify
If i_max  i then
“scambia A[i] e A[i_max]”
...
45
1
A
i 14
34
2
28
3
i_max 34
14 l
4
25 r
5
30
21
15
16
20
8
9
10
11
12
22
12
6
7
Un esempio di applicazione di Heapify
If i_max  i then
“scambia A[i] e A[i_max]”
Heapify(A,i_max)
45
1
A
34
28
2
3
i 14
4
l 30
8
r 21
9
25
22
12
5
6
7
15
16
20
10
11
12
Un esempio di applicazione di Heapify
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
45
1
A
i_max
l 30
8
34
28
2
3
i 14
4
r 21
9
25
22
12
5
6
7
15
16
20
10
11
12
Un esempio di applicazione di Heapify
If i_max  i then
“scambia A[i] e A[i_max]”
...
45
1
A
i_max
l 14
30
8
34
28
2
3
i 14
30
4
r 21
9
25
22
12
5
6
7
15
16
20
10
11
12
Un esempio di applicazione di Heapify
If i_max  i then
“scambia A[i] e A[i_max]”
Heapify(A,i_max)
45
1
34
28
2
3
30
25
22
12
4
5
6
7
A
i
14
21
15
16
20
8
9
10
11
12
Un esempio di applicazione di Heapify
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
45
I test sono falsi
l > heapsize(A)
r > heapsize(A)
per cui i_max = i
(caso base)
1
34
28
2
3
30
25
22
12
4
5
6
7
A
i
14
21
15
8
9
10
16 Heapify
20 termina!
11 Ora12
vale la proprietà heap
Complessità di Heapify
T(n) = max[O(1),O(1)+T(n’)]
Heapify(A,i)
l = LeftRoot(i)
r = RightRoot(i)
O(1)
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
O(1) “scambia A[i] e A[i_max]”
Heapify(A,i_max)
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 n
Sottoalbero completo
di altezza h-1
Sottoalbero completo
di altezza h-2
45
1
n’
34
28
2
n’’
3
30
25
22
12
4
5
6
7
14
21
15
16
8
9
10
11
n’/n è massimo
Complessità di Heapify
45
1
n’
34
28
2
n’’
3
30
25
22
12
4
5
6
7
14
21
15
8
9
10
n’/n non è massimo
(n’ è più piccolo!)
Complessità di Heapify
45
1
n’
34
28
2
n’’
3
30
25
22
12
4
5
6
7
14
21
15
16
20
8
9
10
11
12
n’/n non è massimo
(n è più grande!)
Complessità di Heapify
Sottoalbero completo
di altezza h-1
Sottoalbero completo
di altezza h-2
45
1
n’
34
28
2
n’’
3
30
25
22
12
4
5
6
7
14
21
15
16
8
9
10
11
n’ = 2h - 1
n’’ = 2h-1 - 1
n = 1 + n’ + n’’ = 32h-1 - 1
n’/n = 2h-1/(3 2h-1 -1)  2/3
Complessità di Heapify
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)
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
i=6
1
2
3
4
5
6
7
8
9
10 11
12
14 45 28 34 15 20 12 30 21 25 16 22
14
1
45
28
2
3
34
15
20
12
4
5
6
7
30
21
25
16
22
8
9
10
11
12
BuildHeap(A)
For i = length(A)/2 downto 1 do
Heapify(A,i)
Un esempio di applicazione di BuildHeap
i=6
1
2
3
4
5
6
7
8
9
10 11
12
14 45 28 34 15 22 12 30 21 25 16 20
14
1
45
28
2
3
heap
34
15
22
20
12
4
5
6
7
30
21
25
16
22
20
8
9
10
11
12
BuildHeap(A)
For i = length(A)/2 downto 1 do
Heapify(A,i)
Un esempio di applicazione di BuildHeap
i=5
1
2
3
4
5
6
7
8
9
10 11
12
14 45 28 34 15 20 12 30 21 25 16 22
14
1
45
28
2
3
34
15
22
12
4
5
6
7
30
21
25
16
20
8
9
10
11
12
BuildHeap(A)
For i = length(A)/2 downto 1 do
Heapify(A,i)
Un esempio di applicazione di BuildHeap
i=5
1
2
3
4
5
6
7
8
9
10 11
12
14 45 28 34 25 20 12 30 21 15 16 22
14
heap
1
45
28
2
3
34
15
25
22
12
4
5
6
7
30
21
25
15
16
20
8
9
10
11
12
i=5
BuildHeap(A)
For i = length(A)/2 downto 1 do
Heapify(A,i)
Un esempio di applicazione di BuildHeap
i=4
1
2
3
4
5
6
7
8
9
10 11
12
14 45 28 34 15 20 12 30 21 25 16 22
14
1
heap
45
28
2
3
34
25
22
12
4
5
6
7
30
21
15
16
20
8
9
10
11
12
BuildHeap(A)
For i = length(A)/2 downto 1 do
Heapify(A,i)
Un esempio di applicazione di BuildHeap
i=3
1
2
3
4
5
6
7
8
9
10 11
12
14 45 28 34 15 20 12 30 21 25 16 22
14
1
45
28
heap
2
3
34
25
22
12
4
5
6
7
30
21
15
16
20
8
9
10
11
12
BuildHeap(A)
For i = length(A)/2 downto 1 do
Heapify(A,i)
Un esempio di applicazione di BuildHeap
i=2
1
2
3
4
5
6
7
8
9
10 11
12
14 45 28 34 15 20 12 30 21 25 16 22
14
1
heap
45
28
2
3
34
25
22
12
4
5
6
7
30
21
15
16
20
8
9
10
11
12
BuildHeap(A)
For i = length(A)/2 downto 1 do
Heapify(A,i)
Un esempio di applicazione di BuildHeap
i=1
1
2
3
4
5
6
7
8
9
10 11
12
14 45 28 34 15 20 12 30 21 25 16 22
14
1
45
28
2
3
34
25
22
12
4
5
6
7
30
21
15
16
20
8
9
10
11
12
BuildHeap(A)
For i = length(A)/2 downto 1 do
Heapify(A,i)
Un esempio di applicazione di BuildHeap
i=1
1
2
3
4
5
6
7
8
9
10 11
12
45 14 28 34 15 20 12 30 21 25 16 22
14
45
1
45
14
28
2
3
34
25
22
12
4
5
6
7
30
21
15
16
20
8
9
10
11
12
BuildHeap(A)
For i = length(A)/2 downto 1 do
Heapify(A,i)
Un esempio di applicazione di BuildHeap
i=1
1
2
3
4
5
6
7
8
9
10 11
12
45 34 28 14 15 20 12 30 21 25 16 22
45
14
1
34
28
2
3
34
14
25
22
12
4
5
6
7
30
21
15
16
20
8
9
10
11
12
BuildHeap(A)
For i = length(A)/2 downto 1 do
Heapify(A,i)
Un esempio di applicazione di BuildHeap
i=1
1
2
3
4
5
6
7
8
9
10 11
12
45 34 28 30 15 20 12 14 21 25 16 22
45
14
1
34
28
2
3
30
25
22
12
4
5
6
7
30
14
21
15
16
20
8
9
10
11
12
BuildHeap(A)
For i = length(A)/2 downto 1 do
Heapify(A,i)
Un esempio di applicazione di BuildHeap
i=1
1
2
3
4
5
6
7
8
9
10 11
12
45 34 28 30 15 20 12 14 21 25 16 22
45
14
1
heap
34
28
2
3
30
25
22
12
4
5
6
7
14
21
15
16
20
8
9
10
11
12
BuildHeap(A)
For i = length(A)/2 downto 1 do
Heapify(A,i)
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 BuildHeap
BuildHeap 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
• …
14
h+1
• n/2 volte su heap di altezza h
1
45
28
2
3
34
15
20
12
4
5
6
7
30
21
25
16
22
8
9
10
11
12
Complessità di BuildHeap
Poiché TH = O(log n) e h  log n
n
 n 
f (n)    h1  O(h)  O

h 1  2
2
n  h 
 O  h 
 2 h 0 2 
log n 

log n 

h 1
h

h 
2 
 n 1/ 2 
x ,
  O(n)
Poiché  hx 
f (n)  O
2
2
 2 (1  1 / 2) 
(1  x)
h 0
h
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
SelectSort(n,A)
For j = n downto 2 do
j_ max = FindMax(A,j)
“scambia A[j_max] e A[j]”
HeapSort(A)
BuildHeap(A)
For j = n downto 2 do
“scambia A[1] e A[j]”
Heapify(A[1,…,j-1],1)
{ heapsize(A) = j }
{ j_ max = 1 }
{ ripristina lo heap, ridotto}
Intuizioni su HeapSort
n
1
disordinati
costruisci heap
max
1
parzialmente ordinati
heap
max
i
scambio
+
n Heapify
1
parzialmente ordinati
heap
n
ordinati
Un esempio di esecuzione di HeapSort
HeapSort(A)
BuildHeap(A)
…
45
14
1
45
34
28
2
3
30
34
25
15
22
20
12
4
5
6
7
14
30
21
15
25
16
20
22
8
9
10
11
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)
j = 12
45
14
20
1
34
45
28
2
3
30
34
25
15
22
20
12
4
5
6
7
14
30
21
15
25
16
20
22
45
8
9
10
11
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)
j = 12
45
14
20
1
34
45
28
2
3
30
34
25
15
22
20
12
4
5
6
7
14
30
21
15
25
16
45
8
9
10
11
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)
j = 12
45
14
20
34
1
34
45
30
28
2
3
21
30
34
25
15
22
20
12
4
5
6
7
14
30
20
21
15
25
16
45
8
9
10
11
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)
j = 11
45
14
16
20
34
1
30
28
2
3
21
25
15
22
20
12
4
5
6
7
14
30
20
15
25
16
34
45
8
9
10
11
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)
j = 11
45
14
16
20
34
1
30
28
2
3
21
25
15
22
20
12
4
5
6
7
14
30
20
15
25
34
45
8
9
10
11
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)
j = 11
30
45
14
20
16
34
1
25
30
28
2
3
21
25
15
16
22
20
12
4
5
6
7
14
30
20
15
25
34
45
8
9
10
11
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)
j = 10
30
15
1
25
28
2
3
21
16
22
20
12
4
5
6
7
14
30
20
15
30
34
45
8
9
10
11
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)
j = 10
30
15
1
25
28
2
3
21
16
22
20
12
4
5
6
7
14
30
20
30
34
45
8
9
10
11
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)
j = 10
28
30
15
1
25
22
28
2
3
21
16
15
22
20
12
4
5
6
7
14
30
20
30
34
45
8
9
10
11
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)
j =9
30
28
20
1
25
22
28
2
3
21
16
15
20
12
4
5
6
7
14
30
28
20
30
34
45
8
9
10
11
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)
j =9
20
1
25
22
28
2
3
21
16
15
20
12
4
5
6
7
14
30
28
30
34
45
8
9
10
11
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)
j =9
20
25
1
25
21
22
28
2
3
21
20
16
15
20
12
4
5
6
7
14
30
28
30
34
45
8
9
10
11
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)
j =8
25
14
1
21
22
28
2
3
20
16
15
20
12
4
5
6
7
25
14
30
28
30
34
45
8
9
10
11
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)
j =8
25
14
1
21
22
28
2
3
20
16
15
20
12
4
5
6
7
25
28
30
34
45
8
9
10
11
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)
j =8
25
14
22
1
21
22
15
28
2
3
20
16
15
14
20
12
4
5
6
7
25
28
30
34
45
8
9
10
11
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)
j =7
22
12
1
21
15
2
3
20
16
14
22
12
4
5
6
7
25
28
30
34
45
8
9
10
11
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)
j =7
12
1
21
15
2
3
20
16
14
4
5
6
22
25
28
30
34
45
7
8
9
10
11
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)
j =7
12
21
1
20
21
15
3
2
12
20
4
16
14
5
6
22
25
28
30
34
45
7
8
9
10
11
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)
j =6
21
14
1
15
20
3
2
12
20
4
16
21
14
5
6
22
25
28
30
34
45
7
8
9
10
11
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)
j =6
21
14
1
15
20
3
2
12
16
4
5
21
22
25
28
30
34
45
6
7
8
9
10
11
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)
j =6
21
14
20
1
15
20
16
3
2
12
16
14
4
5
21
22
25
28
30
34
45
6
7
8
9
10
11
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)
j =5
14
20
1
16
15
2
3
12
20
14
4
5
21
22
25
28
30
34
45
6
7
8
9
10
11
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)
j =5
14
20
1
16
15
2
3
12
4
20
21
22
25
28
30
34
45
5
6
7
8
9
10
11
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)
j =5
14
16
20
1
16
14
15
2
3
12
4
20
21
22
25
28
30
34
45
5
6
7
8
9
10
11
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)
j =4
16
12
1
14
15
2
3
12
16
4
20
21
22
25
28
30
34
45
5
6
7
8
9
10
11
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)
j =4
16
12
1
14
15
2
3
16
20
21
22
25
28
30
34
45
4
5
6
7
8
9
10
11
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)
j =4
16
12
15
1
14
15
12
2
3
16
20
21
22
25
28
30
34
45
4
5
6
7
8
9
10
11
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)
j =3
15
12
1
14
15
12
2
3
16
20
21
22
25
28
30
34
45
4
5
6
7
8
9
10
11
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)
j =3
15
12
1
14
2
15
16
20
21
22
25
28
30
34
45
3
4
5
6
7
8
9
10
11
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)
j =3
15
14
12
1
14
12
2
15
16
20
21
22
25
28
30
34
45
3
4
5
6
7
8
9
10
11
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)
j =2
14
12
1
14
12
2
15
16
20
21
22
25
28
30
34
45
3
4
5
6
7
8
9
10
11
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)
j =2
12
1
14
15
16
20
21
22
25
28
30
34
45
2
3
4
5
6
7
8
9
10
11
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)
j =2
L’array A ora è ordinato!
12
14
15
16
20
21
22
25
28
30
34
45
1
2
3
4
5
6
7
8
9
10
11
12
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
HeapSort(A)
BuildHeap(A)
For j = n downto 2 do
“scambia A[1] e A[j]”
Heapify(A[1,…,j-1],1)
  O(n)
  O(1)
  O(log n)
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