1/32

Algoritmi e Strutture Dati

HEAP

Anno accademico 2004-05

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

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

4/32

Memorizzazione di un heap in un vettore

128

64 72

8 7 12 30

1 6 3

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

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)

7/32

i

A B

IDEA: facciamo scendere il nodo i nell’albero finoa trovare la sua posizione.

?

A Bi

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)

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))

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)) ?

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))

12/32

PQ implementate con Heap

max =max = ??

max =

Heapify( )

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))

14/32

Heap Sort: l’idea. Heap

Heapify

Heap

Heapify... avanti così...

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”

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

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 !!!

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

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

20/32

Analisi di QS nel caso ottimo

Caso ottimo: partizioni bilanciateT(n) = 2T(n/2) + (n)

quindi: T(n) = (nlog(n))

21/32

Analisi di QS nel caso pessimo

Caso pessimo: partizioni sbilanciateT(n) = T(n-1) + (n)

quindi: T(n) = (n2)

ricorsione partition

22/32

Analisi di QS nel caso...... non buono !

90% 10%

T(n) ???

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

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:

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

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

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.

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

29/32

È possibile ordinare in meno di n log(n)

???

ovvero in o(n log(n))

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.

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.

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

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

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.