Algoritmi e Strutture Dati
HEAP
Anno accademico 2004-05
1/32
Heap
128
72
64
8
1
7
6
12
30
3
A={ 128, 64, 72, 8,
1 2 3 4
7, 12, 30, 1,
5 6 7 8
6,
9
3 }
10
A(6) = 12
2/32
Heap: definizione formale
Una Heap è un albero binario quasi completo.
Quasi significa che possono mancare alcune foglie consecutive a
partire dall’ultima foglia di destra.
Per ogni nodo i
Value(i) ≤ value(parent(i))
Nota 1: il massimo si trova nella radice
Nota 2: non c’è nessuna relazione tra il valore di un nodo e quello di
un suo fratello
3/32
Memorizzazione di un heap in un
vettore
128
72
64
8
1
7
6
12
30
3
4/32
Memorizzazione di un heap in un
vettore
Radice
posizione 1
Per ogni nodo in posizione i:
left-child(i)
posizione 2i
right-child(i)
posizione 2i+1
Parent(i) = i/2
5/32
Aggiunta di un elemento (heapify)
i
Heaps
Heap
A
i
B
2i 2i+1
parte del vettore già heapizzato
elemento da aggiungere alla sotto heap (verde)
6/32
IDEA: facciamo scendere
il nodo i nell’albero fino
a trovare la sua posizione.
?
i
A
B
A
Bi
7/32
Heapify(A,i)
Heapify(A,i)
l=left(i)
r=right(i)
if l≤heap-size(A) and A[l]>A[i]
then largest=l
else largest=i
if r≤heap-size(A) and A[r]>A[largest]
then largest=r
if largesti
then Exchange(A[i],A[largest])
Heapify(A,largest)
8/32
Heapify: costo computazionale
Caso pessimo: il nodo si sposta fino ad arrivare alle foglie.
Heapify impiega tempo costante ad ogni livello per sistemare
A[i], A[left(i)] e A[right(i)].
Esegue aggiustamenti locali al massimo height(i) volte dove
height(i) = O(log(n))
9/32
Build-heap(A)
Build-heap(A)
heap-size(A)=length(A)
for i=length(A)/2 downto 1
do heapify(A,i)
Analisi approssimativa:
ogni chiamata a heapify costa O(log(n)).
Chiamiamo heapify O(n) volte,
quindi build-heap = O(nlog(n))
Domanda (esercizio): build-heap = (nlog(n)) ?
10/32
PQ implementate con Heap
Extract-max(A)
if heap-size(A)<1 then "error"
max=A[1]
A[1]=A[heapsize(A)]
heapsize(A)=heapsize(A)-1
Heapify(A,1)
return max
O(log(n))
11/32
PQ implementate con Heap
max = ??
max =
max =
Heapify(
)
12/32
PQ implementate con Heap
Insert(A,x)
heap-size(A)=heap-size(A)+1
i=heap-size(A)
while i>1 and A[parent(i)]<x
do A[i]=A[parent(i)]
i=parent(i)
A[i]=x
O(log(n))
13/32
Heap Sort: l’idea.
Heap
Heapify
Heap
Heapify
... avanti così...
14/32
Heap Sort
Heap-Sort(A)
build-heap(A)
for i=length(A) downto 2
do exchange(A[1],A[i])
heap-size[A]=heap-size(A)-1
heapify(A,1)
O(nlog(n))
È un metodo “in place”
15/32
Quicksort: l’idea
Dividi: Dividi il vettore in due parti non vuote.
Conquista: ordina le due parti ricorsivamente
Combina: fondi le due parti ottenendo un vettore ordinato.
A={10,5,41,3,6,9,12,26}
mergesort
A metà
A1={10,5,41,3} A2={6,9,12,26}
quicksort
Intorno a un Pivot, es 12
A1={10,5,3,6,9,12} A2={41,26}
16/32
Quicksort
Quicksort(A,p,r)
if p<r then
q=partition(A,p,r)
Quicksort(A,p,q)
Quicksort(A,q+1,r)
Nota:
Mergesort lavora dopo la ricorsione
Quicksort lavora prima della ricorsione
Partition è cruciale !!!
17/32
A(p,r)
i
Pivot
j
5 3 2 6 4 1 3 7
i
j
i
j
5 3 2 6 4 1 3 7
3 3 2 6 4 1 5 7
i
j
i
j
3 3 2 6 4 1 5 7
3 3 2 1 4 6 5 7
j
i
3 3 2 1 4 6 5 7
<5
≥5
(n)
in place
18/32
Partition(A,p,r)
x=A[p]
i=p-1
j=r+1
while true do
repeat j=j-1 until A[j]<=x
repeat i=i+1 until A[i]>=x
if i<j then scambia(A[i],A[j])
else return j
19/32
Analisi di QS nel caso ottimo
Caso ottimo: partizioni bilanciate
T(n) = 2T(n/2) + (n)
quindi: T(n) = (nlog(n))
20/32
Analisi di QS nel caso pessimo
Caso pessimo: partizioni sbilanciate
T(n) = T(n-1) + (n)
ricorsione
partition
quindi: T(n) = (n2)
21/32
Analisi di QS nel caso...
... non buono !
90%
10%
T(n) ???
22/32
Albero di ricorsione
n +
n
1/10 n
1/100 n
log10n
9/100 n
n +
9/10 n
9/100 n
81/100 n
81/1000 n
log10/9n
729/1000 n
n +
<n
(n log(n))
23/32
Analisi del caso medio di QS:
una intuizione.
Caso medio: a volte facciamo una buona
partition a volte no...
buona partition:
cattiva partition:
24/32
Caso medio
le buone e le cattive partition si alternano...
1
1
cattiva
n-1
(n-1)/2
(n-1)/2
buona
dopo una cattiva e una buona partizione in
successione siamo più o meno nella situazione in cui
la cattiva partizione non è stata fatta !
25/32
QS: distribuzione degli input
Abbiamo assunto implicitamente che tutte le sequenze di
numeri da ordinare fossero equiprobabili.
Se ciò non fosse vero potremmo avere costi
computazionali più alti.
Possiamo “rendere gli input equiprobabili” ?
come procediamo
mischiamo la sequenza
casualmente prima di ordinare
Scegliamo il pivot a caso.
26/32
QS “randomizzato”
QSR usa una versione randomizzata della procedura
Partition.
Randomized-partition(A,p,r)
i=random(p,r)
exchange(A[p],A[i])
return Partition(A,p,r)
Un algoritmo randomizzato non ha un input pessimo,
bensì ha una sequenza di scelte pessime di pivot.
27/32
Insertion
sort
Merge
sort
Heap
sort
Quick
sort
Caso
pessimo
n2
n log(n)
n log(n)
n2
Caso
medio
n2
n log(n)
n log(n)
n log(n)
Caso
ottimo
n
n log(n)
n log(n)
n log(n)
= in place
28/32
È possibile ordinare in meno di
n log(n)
???
ovvero in o(n log(n))
29/32
Limite inferiore di complessità
Insertion-sort
Merge-sort
Heap-sort
Quick-sort
“Comparison-sort”
algoritmi basati su confronti
Questi metodi calcolano una soluzione che
dipende esclusivamentedall’esito di confronti fra numeri
TEOREMA (Lower Bound per algoritmi Comparison-sort):
Qualsiasi algoritmo “comparison-sort” deve effettuare nel
caso pessimo (n log(n)) confronti per ordinare una sequenza
di n numeri.
30/32
lower bound per comparison sort
IDEA: con n numeri ho n! possibili ordinamenti.
Possiamo scegliere quello giusto tramite una sequenza
di confronti.
≤
≤
>
>
≤
>
Ogni nodo rappresenta un confronto.
31/32
Esempio:
a1:a2
≤
a2:a3
≤
a1,a2,a3
≤
a1,a3,a2
n=3
>
a1:a3
{a1,a2,a3}
>
≤
>
a3,a1,a2
albero dei
confronti
a1:a3
a2,a1,a3
≤
a2,a3,a1
>
a2:a3
>
a3,a2,a1
Ogni nodo bianco rappresenta un confronto.
Ogni nodo rosso rappresenta una possibile soluzione.
32/32
Limite inferiore al numero dei confronti
3! = 6 = numero di foglie dell’albero dei confronti.
ogni (cammino dalla radice ad una) foglia rappresenta un
ordinamento
ci sono n! ordinamenti.
quanto deve essere alto un albero per avere n! foglie ???
un albero binario alto h ha al massimo 2h foglie
dobbiamo avere 2h ≥ n!
Formula di Stirling: n! > (n/e)n e=2.17...
h ≥ log[(n/e)n] = nlog(n) - nlog(e) = (nlog(n))
33/32
Il caso pessimo di un qualsiasi algoritmo comparison-sort
eseguito su una sequenza di n numeri è dato dall’altezza
dell’albero di decisione associato a quell’algoritmo.
MA
Un albero binario con n! foglie (ordinamenti) ha un altezza
(nlog(n))
QUINDI
qualsiasi algoritmo comparison-sort,
nel caso pessimo, esegue (nlog(n)) confronti.
34/32