1/32 algoritmi e strutture dati heap anno accademico 2004-05
TRANSCRIPT
![Page 1: 1/32 Algoritmi e Strutture Dati HEAP Anno accademico 2004-05](https://reader035.vdocumenti.com/reader035/viewer/2022070313/5542eb74497959361e8dc966/html5/thumbnails/1.jpg)
1/32
Algoritmi e Strutture Dati
HEAP
Anno accademico 2004-05
![Page 2: 1/32 Algoritmi e Strutture Dati HEAP Anno accademico 2004-05](https://reader035.vdocumenti.com/reader035/viewer/2022070313/5542eb74497959361e8dc966/html5/thumbnails/2.jpg)
2/32
Heap128
64 72
8 7 12 30
1 6 3
A={ 128, 64, 72, 8, 7, 12, 30, 1, 6, 3 } 1 2 3 4 5 6 7 8 9 10 A(6) = 12
![Page 3: 1/32 Algoritmi e Strutture Dati HEAP Anno accademico 2004-05](https://reader035.vdocumenti.com/reader035/viewer/2022070313/5542eb74497959361e8dc966/html5/thumbnails/3.jpg)
3/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 iValue(i) ≤ value(parent(i))
Nota 1: il massimo si trova nella radiceNota 2: non c’è nessuna relazione tra il valore di un nodo e quello di un suo fratello
![Page 4: 1/32 Algoritmi e Strutture Dati HEAP Anno accademico 2004-05](https://reader035.vdocumenti.com/reader035/viewer/2022070313/5542eb74497959361e8dc966/html5/thumbnails/4.jpg)
4/32
Memorizzazione di un heap in un vettore
128
64 72
8 7 12 30
1 6 3
![Page 5: 1/32 Algoritmi e Strutture Dati HEAP Anno accademico 2004-05](https://reader035.vdocumenti.com/reader035/viewer/2022070313/5542eb74497959361e8dc966/html5/thumbnails/5.jpg)
5/32
Memorizzazione di un heap in un vettore
Radice posizione 1Per ogni nodo in posizione i:left-child(i) posizione 2iright-child(i) posizione 2i+1Parent(i) = i/2
![Page 6: 1/32 Algoritmi e Strutture Dati HEAP Anno accademico 2004-05](https://reader035.vdocumenti.com/reader035/viewer/2022070313/5542eb74497959361e8dc966/html5/thumbnails/6.jpg)
6/32
i
A B
Heaps Heap
i 2i 2i+1
parte del vettore già heapizzato
elemento da aggiungere alla sotto heap (verde)
Aggiunta di un elemento (heapify)
![Page 7: 1/32 Algoritmi e Strutture Dati HEAP Anno accademico 2004-05](https://reader035.vdocumenti.com/reader035/viewer/2022070313/5542eb74497959361e8dc966/html5/thumbnails/7.jpg)
7/32
i
A B
IDEA: facciamo scendere il nodo i nell’albero finoa trovare la sua posizione.
?
A Bi
![Page 8: 1/32 Algoritmi e Strutture Dati HEAP Anno accademico 2004-05](https://reader035.vdocumenti.com/reader035/viewer/2022070313/5542eb74497959361e8dc966/html5/thumbnails/8.jpg)
8/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 largesti then Exchange(A[i],A[largest])
Heapify(A,largest)
![Page 9: 1/32 Algoritmi e Strutture Dati HEAP Anno accademico 2004-05](https://reader035.vdocumenti.com/reader035/viewer/2022070313/5542eb74497959361e8dc966/html5/thumbnails/9.jpg)
9/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))
![Page 10: 1/32 Algoritmi e Strutture Dati HEAP Anno accademico 2004-05](https://reader035.vdocumenti.com/reader035/viewer/2022070313/5542eb74497959361e8dc966/html5/thumbnails/10.jpg)
10/32
Build-heap(A)
Build-heap(A)heap-size(A)=length(A) for i=length(A)/2 downto 1do 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)) ?
![Page 11: 1/32 Algoritmi e Strutture Dati HEAP Anno accademico 2004-05](https://reader035.vdocumenti.com/reader035/viewer/2022070313/5542eb74497959361e8dc966/html5/thumbnails/11.jpg)
11/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))
![Page 12: 1/32 Algoritmi e Strutture Dati HEAP Anno accademico 2004-05](https://reader035.vdocumenti.com/reader035/viewer/2022070313/5542eb74497959361e8dc966/html5/thumbnails/12.jpg)
12/32
PQ implementate con Heap
max =max = ??
max =
Heapify( )
![Page 13: 1/32 Algoritmi e Strutture Dati HEAP Anno accademico 2004-05](https://reader035.vdocumenti.com/reader035/viewer/2022070313/5542eb74497959361e8dc966/html5/thumbnails/13.jpg)
13/32
PQ implementate con Heap
Insert(A,x)heap-size(A)=heap-size(A)+1i=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))
![Page 14: 1/32 Algoritmi e Strutture Dati HEAP Anno accademico 2004-05](https://reader035.vdocumenti.com/reader035/viewer/2022070313/5542eb74497959361e8dc966/html5/thumbnails/14.jpg)
14/32
Heap Sort: l’idea. Heap
Heapify
Heap
Heapify... avanti così...
![Page 15: 1/32 Algoritmi e Strutture Dati HEAP Anno accademico 2004-05](https://reader035.vdocumenti.com/reader035/viewer/2022070313/5542eb74497959361e8dc966/html5/thumbnails/15.jpg)
15/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”
![Page 16: 1/32 Algoritmi e Strutture Dati HEAP Anno accademico 2004-05](https://reader035.vdocumenti.com/reader035/viewer/2022070313/5542eb74497959361e8dc966/html5/thumbnails/16.jpg)
16/32
Quicksort: l’idea
Dividi: Dividi il vettore in due parti non vuote.Conquista: ordina le due parti ricorsivamenteCombina: fondi le due parti ottenendo un vettore ordinato.
A={10,5,41,3,6,9,12,26}
mergesort
quicksort
A metàA1={10,5,41,3} A2={6,9,12,26}
Intorno a un Pivot, es 12A1={10,5,3,6,9,12} A2={41,26}D
ivi d
i
![Page 17: 1/32 Algoritmi e Strutture Dati HEAP Anno accademico 2004-05](https://reader035.vdocumenti.com/reader035/viewer/2022070313/5542eb74497959361e8dc966/html5/thumbnails/17.jpg)
17/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 ricorsioneQuicksort lavora prima della ricorsionePartition è cruciale !!!
![Page 18: 1/32 Algoritmi e Strutture Dati HEAP Anno accademico 2004-05](https://reader035.vdocumenti.com/reader035/viewer/2022070313/5542eb74497959361e8dc966/html5/thumbnails/18.jpg)
18/32
5 3 2 6 4 1 3 7
5 3 2 6 4 1 3 7
3 3 2 6 4 1 5 7
3 3 2 6 4 1 5 7
3 3 2 1 4 6 5 7
3 3 2 1 4 6 5 7
i j
i
i
i
i
i
j
j
j
j
j
A(p,r)
< 5 ≥ 5
Pivot
(n)in place
![Page 19: 1/32 Algoritmi e Strutture Dati HEAP Anno accademico 2004-05](https://reader035.vdocumenti.com/reader035/viewer/2022070313/5542eb74497959361e8dc966/html5/thumbnails/19.jpg)
19/32
Partition(A,p,r)x=A[p]i=p-1j=r+1while true do
repeat j=j-1 until A[j]<=xrepeat i=i+1 until A[i]>=xif i<j then scambia(A[i],A[j])
else return j
![Page 20: 1/32 Algoritmi e Strutture Dati HEAP Anno accademico 2004-05](https://reader035.vdocumenti.com/reader035/viewer/2022070313/5542eb74497959361e8dc966/html5/thumbnails/20.jpg)
20/32
Analisi di QS nel caso ottimo
Caso ottimo: partizioni bilanciateT(n) = 2T(n/2) + (n)
quindi: T(n) = (nlog(n))
![Page 21: 1/32 Algoritmi e Strutture Dati HEAP Anno accademico 2004-05](https://reader035.vdocumenti.com/reader035/viewer/2022070313/5542eb74497959361e8dc966/html5/thumbnails/21.jpg)
21/32
Analisi di QS nel caso pessimo
Caso pessimo: partizioni sbilanciateT(n) = T(n-1) + (n)
quindi: T(n) = (n2)
ricorsione partition
![Page 22: 1/32 Algoritmi e Strutture Dati HEAP Anno accademico 2004-05](https://reader035.vdocumenti.com/reader035/viewer/2022070313/5542eb74497959361e8dc966/html5/thumbnails/22.jpg)
22/32
Analisi di QS nel caso...... non buono !
90% 10%
T(n) ???
![Page 23: 1/32 Algoritmi e Strutture Dati HEAP Anno accademico 2004-05](https://reader035.vdocumenti.com/reader035/viewer/2022070313/5542eb74497959361e8dc966/html5/thumbnails/23.jpg)
23/32
Albero di ricorsione
n
1/10 n 9/10 n
1/100 n 9/100 n 9/100 n 81/100 n
n +
n +
n +
(n log(n))
< n 81/1000 n 729/1000 nlog10n
log10/9n
![Page 24: 1/32 Algoritmi e Strutture Dati HEAP Anno accademico 2004-05](https://reader035.vdocumenti.com/reader035/viewer/2022070313/5542eb74497959361e8dc966/html5/thumbnails/24.jpg)
24/32
Analisi del caso medio di QS:una intuizione.
Caso medio: a volte facciamo una buona partition a volte no...
buona partition:cattiva partition:
![Page 25: 1/32 Algoritmi e Strutture Dati HEAP Anno accademico 2004-05](https://reader035.vdocumenti.com/reader035/viewer/2022070313/5542eb74497959361e8dc966/html5/thumbnails/25.jpg)
25/32
Caso medio
le buone e le cattive partition si alternano...
cattiva1 n-1
1 (n-1)/2 (n-1)/2
dopo una cattiva e una buona partizione in successione siamo più o meno nella situazione in cui la cattiva partizione non è stata fatta !
buona
![Page 26: 1/32 Algoritmi e Strutture Dati HEAP Anno accademico 2004-05](https://reader035.vdocumenti.com/reader035/viewer/2022070313/5542eb74497959361e8dc966/html5/thumbnails/26.jpg)
26/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” ?
mischiamo la sequenzacasualmente prima di ordinare
Scegliamo il pivot a caso.
come procediamo
![Page 27: 1/32 Algoritmi e Strutture Dati HEAP Anno accademico 2004-05](https://reader035.vdocumenti.com/reader035/viewer/2022070313/5542eb74497959361e8dc966/html5/thumbnails/27.jpg)
27/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.
![Page 28: 1/32 Algoritmi e Strutture Dati HEAP Anno accademico 2004-05](https://reader035.vdocumenti.com/reader035/viewer/2022070313/5542eb74497959361e8dc966/html5/thumbnails/28.jpg)
28/32
Insertionsort
Mergesort
Heapsort
Quicksort
Caso pessimo
n2 n log(n) n log(n) n2
Caso medio
n2 n log(n) n log(n) n log(n)
Casoottimo
n n log(n) n log(n) n log(n)
= in place
![Page 29: 1/32 Algoritmi e Strutture Dati HEAP Anno accademico 2004-05](https://reader035.vdocumenti.com/reader035/viewer/2022070313/5542eb74497959361e8dc966/html5/thumbnails/29.jpg)
29/32
È possibile ordinare in meno di n log(n)
???
ovvero in o(n log(n))
![Page 30: 1/32 Algoritmi e Strutture Dati HEAP Anno accademico 2004-05](https://reader035.vdocumenti.com/reader035/viewer/2022070313/5542eb74497959361e8dc966/html5/thumbnails/30.jpg)
30/32
Limite inferiore di complessità
Insertion-sortMerge-sortHeap-sortQuick-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.
![Page 31: 1/32 Algoritmi e Strutture Dati HEAP Anno accademico 2004-05](https://reader035.vdocumenti.com/reader035/viewer/2022070313/5542eb74497959361e8dc966/html5/thumbnails/31.jpg)
31/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.
![Page 32: 1/32 Algoritmi e Strutture Dati HEAP Anno accademico 2004-05](https://reader035.vdocumenti.com/reader035/viewer/2022070313/5542eb74497959361e8dc966/html5/thumbnails/32.jpg)
32/32
Esempio: n=3 {a1,a2,a3}
a1:a2
a2:a3 a1:a3
a1,a2,a3 a1:a3 a2,a1,a3 a2:a3
≤ >
>>≤ ≤
Ogni nodo bianco rappresenta un confronto. Ogni nodo rosso rappresenta una possibile soluzione.
a1,a3,a2 a3,a1,a2
>≤
a2,a3,a1 a3,a2,a1
>≤
albero dei confronti
![Page 33: 1/32 Algoritmi e Strutture Dati HEAP Anno accademico 2004-05](https://reader035.vdocumenti.com/reader035/viewer/2022070313/5542eb74497959361e8dc966/html5/thumbnails/33.jpg)
33/32
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))
Limite inferiore al numero dei confronti
![Page 34: 1/32 Algoritmi e Strutture Dati HEAP Anno accademico 2004-05](https://reader035.vdocumenti.com/reader035/viewer/2022070313/5542eb74497959361e8dc966/html5/thumbnails/34.jpg)
34/32
Il caso pessimo di un qualsiasi algoritmo comparison-sort eseguito su una sequenza di n numeri è dato dall’altezzadell’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.