Algoritmi e Strutture Dati - dis.uniroma1.itlaura/assets/files/slideasd/cap8.pdf · Struttura: è...

Code con priorità

Algoritmi e Strutture Dati

Luigi Laura

Luigi LauraAlgoritmi e strutture dati

da Demetrescu et al. McGraw Hill 20042

Tipo di dato CodaPriorità (1/2)



Tipo di dato CodaPriorità (2/2)



Tre implementazioni

d-heap: generalizzazione degli heapbinari visti per l’ordinamento

heap binomiali

heap di Fibonacci



d-heap



Definizione

Un d-heap è un albero radicato d-ario con le seguentiproprietà:

1. Struttura: è completo almeno fino al penultimolivello

2. Contenuto informativo: ogni nodo v contiene unelemento elem(v) ed una chiave chiave(v) presa daun dominio totalmente ordinato

3. Ordinamento a heap: per ogni nodo v (diversodalla radice) chiave(v) ≥ chiave(parent(v))



Esempio

Heap d-ario con 18 nodi e d = 3



Proprietà

1. Un d-heap con n nodi ha altezza O(logd n)

2. La radice contiene l’elemento con chiave minima(per via della proprietà di ordinamento a heap)

3. Può essere rappresentato implicitamente tramitevettore posizionale grazie alla proprietà di struttura



Procedure ausiliarie

Utili per ripristinare la proprietà di ordinamento a heapsu un nodo v che non la soddisfi T(n) = O(logd n)

T(n) = O(d logd n)



findMin

T(n) = O(1)



insert(elem e, chiave k)

T(n) = O(logd n) ( muoviAlto )



delete(elem e) e deleteMin

T(n) = O(d logd n) ( muoviBasso )

Può essere usata anche per implementare cancellazionedel minimo



decreaseKey(elem e, chiave d)

T(n) = O(logd n) ( muoviAlto )



increaseKey(elem e, chiave d)

T(n) = O(d logd n) ( muoviBasso )



Heap binomiali



Alberi binomialiAlbero binomiale Bh (definito ricorsivamente) :1. B0 consiste di un unico nodo2. Per i ≥ 0, Bi+1 ottenuto fondendo due alberi binomiali

Bi con radice di uno figlia della radice dell’altro



Proprietà strutturali



Definizione di heap binomiale

Un heap binomiale è una foresta di alberi binomialicon le seguenti proprietà:

1. Struttura: ogni albero Bi nella foresta è un alberobinomiale

2. Unicità: per ogni i, esiste al più un Bi nella foresta3. Contenuto informativo: ogni nodo v contiene un

elemento elem(v) ed una chiave chiave(v) presa daun dominio totalmente ordinato

4. Ordinamento a heap: per ogni nodo v (diverso dauna delle radici) chiave(v) ≥ chiave(parent(v))



Proprietà

In un heap binomiale con n nodi, vi sono alpiù log2 n alberi binomiali, ciascuno congrado ed altezza O(log n)



Procedura ausiliaria

Utile per ripristinare la proprietà di unicità in un heapbinomiale

T(n) è proporzionale al numero di alberi binomiali in input



Realizzazione (1/3)



Realizzazione (2/3)



Realizzazione (3/3)

Tutte le operazioni richiedono tempo T(n) = O(log n)Durante l’esecuzione della procedura ristruttura esistonoinfatti al più tre Bi, per ogni i ≥ 0



Analisi Ammortizzata



Metodologie di analisi di algoritmi

Finora abbiamo visto tre tipi di analisi:

• Analisi nel caso peggiore

• Analisi nel caso medio

• Analisi nel caso atteso (algoritmi randomizzati)

Ne vedremo un altro:

• Analisi ammortizzata



Analisi ammortizzata• Strutture dati con garanzia assoluta sui loro

tempi di esecuzione: analisi di caso peggioreper operazione (esempio: analisi di heap inheapsort)

• Analisi ammortizzata:• non ci interessa tanto caratterizzare tempo richiesto nel

caso peggiore da un’operazione sulla struttura dati• quanto caratterizzare tempo totale richiesto dalle

operazioni sulla struttura dati• ovvero tempo medio di un’operazione, dove la media è

sulla sequenza di operazioni



Analisi ammortizzata

• Supponiamo di avere una sequenza di σoperazioni su una particolare struttura dati

• La sequenza richiede tempo totale O(σ t) peressere eseguita

• Diremo che il tempo ammortizzato per ognioperazione della sequenza è O(t)

• Media sulla sequenza: O(σ t) / σ = O(t)• Nota: una singola operazione potrebbe

richiedere più di O(t) nel caso peggiore!



Analisi ammortizzata

• Sequenza di σ operazioni richiede tempo O(σt)

• Tempo ammortizzato: O(σ t) / σ = O(t)• OK per molte applicazioni• Abbiamo bisogno di utilizzare strutture dati su

sequenze di operazioni• Analizzare prestazioni su sequenze di

prestazioni



Esempio 1

Pila con le seguenti due operazioni• push(x): push elemento x sulla pila• multipop(k): esegui k pop sulla pila (se la pila

ha almeno k elementi)Analisi nel caso peggiore:• push(x): O(1)• multipop(k): O( min{ k, |P| } ) = O(n) dove |P|

è la dimensione della pila



Esempio 1

Analisi nel caso peggiore:• push(x): O(1)• multipop(k): O( min { k, |P| } ) = O(n) dove |P| è

la dimensione della pilaQuanto tempo richiederà una sequenza di σ

operazioni? O(σ n) ?No!



Analisi ammortizzata dell’Esempio 1

Intuizione:• Prima di togliere un elemento x con una

multipop dobbiamo averlo inserito con unapush(x)

• Ogni sequenza di σ push e multipop richiede intotale tempo O(σ )

• Tempo ammortizzato per operazione:O(σ ) / σ = Ο(1)

• Vedremo un’analisi più formale di questo



Metodologie di analisi ammortizzata

Tre tipologie di analisi diverse:• Metodo cumulativo:

Sequenza di σ operazioni richiede tempo O(σ t)Tempo ammortizzato: O(σ t) / σ = O(t)

• Metodo del banchiere:Per eseguire un passo dobbiamo pagare 1 EURAllocare EUR in modo da pagare per tutti i passi

• Metodo del potenziale:Analogia con analisi potenziale (Fisica)



Metodo del Banchiere per Esempio 1Quando esegui push(x) “sborsa” 2 EUR:• 1 EUR per pagare lavoro richiesto da push(x)• 1 EUR conservato nell’elemento xQuando esegui multipop(k) “sborsa” 0 EUR:• lavoro richiesto da multipop(k) pagato dagli

EUR conservati negli elementi!1. Per ogni operazione “sborsi” al più O(1) EUR2. Tutti gli EUR “sborsati” sufficienti a pagare per

lavoro richiesto dalle operazioni



Metodo del PotenzialeDefinisci potenziale Φ per struttura dati D

Φ(D) misura potenzialità di D ad eseguire lavoro(configurazione attuale)

Durante operazione i-esima, struttura dati passa daconfigurazione Di a configurazione Di+1

Passa da potenziale Φ(Di) a potenziale Φ(Di+1)Tenere in conto variazione di potenziale

Δ Φ = Φ(Di+1) - Φ(Di)Operazione può essere molto costosa ma mette strutturadati in grado di eseguire più efficientemente operazionifuture (costo operazione compensato da Δ Φ )



Metodo del PotenzialeTipicamente potenziale Φ soddisfa le:

Φ(D0) = 0 e Φ(Di) ≥ 0 per ogni i Definiamo tempo ammortizzato ai dell’operazione i-

esima: ai = ti + Φ(Di+1) - Φ(Di) dove ti è il tempo (attuale) operazione i-esima Sommando su sequenza di operazioni

Σi ai = Σi ti + Σi ( Φ(Di+1) - Φ(Di) ) Σi ai = Σi ti + ( Φ(Dn) - Φ(D0) ) Σi ai ≥ Σi ti



Metodo del Potenziale per Esempio 1

Definiamo potenziale Φ della pila P: Φ(P) = |P|Nota che: Φ(P0) = 0 e Φ(Pi) ≥ 0 per ogni i

Tempo ammortizzato ai di operazione i-esima: ai = ti + Φ(Di+1) - Φ(Di)

Costo ammortizzato di push(x) : ai = ti + Φ(Di+1) - Φ(Di) = 1 + 1 = 2 Costo ammortizzato di multipop(k) : ai = ti + Φ(Di+1) - Φ(Di) = k + ( -k) = 0



Heap di Fibonacci



Heap di FibonacciHeap binomiale rilassato: si ottiene da un heap

binomiale rilassando la proprietà di unicità dei Bied utilizzando un atteggimento più “pigro” durantel’operazione insert (perché ristrutturare subito laforesta quando potremmo farlo dopo?)

Heap di Fibonacci: si ottiene da un heap binomialerilassato rilassando la proprietà di struttura dei Biche non sono più necessariamente alberi binomiali

Analisi sofisticata: i tempi di esecuzione sonoammortizzati su sequenze di operazioni



Conclusioni: tabella riassuntiva

L’analisi di DHeap e HeapBinomiale è nel casopeggiore, mentre quella per HeapBinomialeRilassato eHeapFibonacci è ammortizzata

Algoritmi e Strutture Dati - dis.uniroma1.itlaura/assets/files/slideasd/cap8.pdf · Struttura: è...

Documents

Transcript of Algoritmi e Strutture Dati - dis.uniroma1.itlaura/assets/files/slideasd/cap8.pdf · Struttura: è...