Home

Federica EU

1/21

Massimo Benerecetti » 5.L'algoritmo di ordinamento HeapSort II

Heapify: tempo di esecuzione

Procediamo ora allo studio del tempo di esecuzione dell’algoritmo Heapify.
Un primo risultato dell’analisi si può ottenere osservando che ogni chiamata dell’algoritmo può effettuare al massimo una chiamata ricorsiva, o sul sottoalbero destro o sul sinistro.
Questo significa che, nel caso peggiore, una esecuzione di Heapify può al massimo generare tante chiamate ricorsive quanti sono i nodi lungo il percorso più lungo dell’albero su cui è eseguito.
La lunghezza del percorso più lungo in un albero corrisponde all’altezza dell’albero.
Ogni chiamata ricorsiva effettua localmente un numero di operazioni elementari costante.
Quindi, detta h l’altezza dell’albero su cui è chiamato Heapify, il tempo di esecuzione in funzione dell’altezza dell’albero sarà, alla peggio, proporzionale a h, cioè T(h) = O(h).

Heapify: tempo di esecuzione (segue)

Poiché gli alberi su cui opera Heapify sono alberi completi, l’altezza di questi alberi è uguale al logaritmo del numero dei nodi che contengono, otteniamo che il tempo di esecuzione in funzione di n sarà T(n) = O(log₂n).
Nelle slide successive procederemo al calcolo del tempo di esecuzione di Heapify provando ad applicare le tecniche di analisi per gli algoritmi ricorsivi introdotte nella Lezione 3.
Inizieremo con la definizione dell’equazione di ricorrenza indotta dall’algoritmo.
Osservate che, guardando semplicemente l’algoritmo, non è immediato individuare la relazione tra la dimensione dell’albero (l’input) di una chiamata e quello che essa passa alla chiamata ricorsiva che eventualmente genera.

Heapify: tempo di esecuzione (segue)

Analisi del tempo di esecuzione di Heapify.

Heapify: tempo di esecuzione (segue)

Analisi del tempo di esecuzione di Heapify.

Heapify: tempo di esecuzione (segue)

Detto n il numero di elementi nel sottoalbero su cui Heapify è chiamato, l’equazione di ricorrenza risulterebbe quindi della forma:

T(n) = T(?) + O(1)

Al fine di poter calcolare il tempo nel caso peggiore, è necessario individuare la relazione tra n e il numero massimo di nodi su cui Heapify può essere richiamato ricorsivamente.
Si può dimostrare che, nel caso peggiore, ad ogni chiamata ricorsiva Heapify viene eseguito su un numero di nodi che è minore dei 2/3 del numero di nodi correnti n.
Assumendo, quindi, che il sottoalbero più grande sia il sinistro, il numero di nodi n_s del sottoalbero su cui Heapify è chiamato ricorsivamente è al più $\frac{2}{3} n$ $\Biggl(n_{s} \leq \frac{2}{3} n\Biggr)$ (analogo ragionamento si può fare se fosse il destro)
Nelle tre slide successive mostreremo che questi è il caso.

Heapify: tempo di esecuzione (segue)

L’albero completo che massimizza il rapporto $\frac{n_{s}}{n}$ è riportato nella figura a fianco.
Detta h l’altezza dell’albero, entrambi i sottoalberi sinistro e destro sono alberi pieni, rispettivamente di altezza h-1 e h-2.

Forma dell'albero completo che massimizza il rapporto n_s/n

Heapify: tempo di esecuzione (segue)

Per verificare l’asserto precedente, è sufficiente osservare quanto segue.

Se eliminiamo dall’albero della slide precedente una foglia del sottoalbero sinistro pieno, otteniamo che il rapporto $\frac{\overbar{n}_{s}}{\overbar{n}}$ dell’albero così ottenuto diminuisce. Infatti:

$\overbar{n}_{s} = n_{s}-1~~~~~;~~~~~\overbar{n} = n-1$

quindi

$\frac{\overbar{n}_{s}}{\overbar{n}} = \frac{n_{s}-1}{n-1} \leq \frac{n_{s}}{n}$

analogamente, se aggiugiamo una foglia al sottoalbero destro, il nuovo rapporto che otteniamo sarà

$\frac{\overbar{n}_{s}}{\overbar{n}} = \frac{n_{s}}{n-1} \leq \frac{n_{s}}{n}$

segue quindi che il valore massimo del rapporto si ottiene proprio quando l’albero ha la forma dell’albero nella slide precedente.

Analisi del caso peggiore di Heapify.

Heapify: tempo di esecuzione (segue)

Per ricavare la relazione, nel caso peggiore, tra la dimensione dell’input ricevuto dalla chiamata ricorsiva di Heapify rispetto alla dimensione dell’input di partenza, è sufficiente osservare che: se l’altezza dell’albero in figura è h, allora l’altezza del sottoablero sinistro è h-1 e quella del sottoalbero destro è h-2, quindi

$n_{s} = 2^{h}-1~~~~~;~~~~~n_{d} = 2^{h-1}-1$ .

Inoltre $n = n_{s} + n_{d} + 1$ avremo quindi che $n = 2^{h}-1 + 2^{h-1}-1 + 1 = 3\cdot 2^{h-1}-1$ il rapporto desiderato è

$\frac{n_{s}}{n} = \frac{2^{h}-1}{3\cdot 2^{h-1}-1} = \frac{2\cdot 2^{h-1}-1}{3\cdot 2^{h-1}-1} < \frac{2}{3}$

poiché quando $x< y$ vale $\frac{x-1}{y-1} < \frac{x}{y}$ .

Possiamo quindi concludere che se n è il numero di nodi della chiamata principale ad Heapify, allora la chiamata ricorsiva verrà eseguita su di un sottoalbero che conterrà non più di $\frac{2}{3}n$ nodi.

Analisi del caso peggiore di Heapify.

Heapify: tempo di esecuzione (segue)

T(n) = max(O(1),max(O(1),T(?) + O(1))
……….. $\leq max(O(1),max(O(1),T(\frac{2}{3}n) + O(1))$
……….. $\leq T(\frac{2}{3}n) + \Theta(1)$
Posto
T’(n) = T’(2n/ 3) + θ(1)
risolvendo l’equazione di ricorrenza per T’(n) con gli alberi di ricorrenza otteniamo:

$T'(n) = \Theta(log n)$

da cui, essendo T’(n) un estremo superiore asintotico per T(n), otteniamo:

T(n) = O(log n)

Costruzione di uno Heap

Il passo successivio è quello della costruzione di uno Heap a partire da una sequenza arbitraria in input.
L’algoritmo Costruisci-Heap(A) utilizza l’algoritmo Heapify per inserire ogni elemento dell’array A in uno Heap, risistemando sul posto gli elementi tramite opportuni scambi.
Osserviamo innanzitutto che, data la corrispondenza tra un array ed un albero completo:

gli ultimi [n/2] elementi dell’array corrispondono alle foglie, sono cioè radici di sottoalberi vuoti i quali sono ovviamente già degli Heap
è, quindi, sufficiente ripristinare la proprietà heap solo per i primi [n/2] elementi, utilizzando Heapify.

L’algoritmo seguente implementa le intuizioni appena esposte:

Costruisci-Heap(A) heapsize[A] = length[A] FOR i = _length[A]/2_ DOWNTO 1 DO Heapify(A,i)
La variabile heapsize[A] conterrà la dimensione dello Heap, inizialmente pari alla dimensione n=length[A] della sequenza in input.

Esempio

Esempio di costruzione di uno Heap.

CostruisciHeap: esempio di applicazione

Esempio di applicazione di CostruisciHeap: simulazione.

Risultato dell’esempio

Risultato finale dell'applicazione di CostruisciHeap.

Tempo di esecuzione di CostruisciHeap

Possiamo facilmente calcolare un limite superiore asintotico al tempo di esecuzione di Costruisci-Heap, osservando che:

l’algoritmo esegue [n/2] chiamate a Heapify all’interno del ciclo for
ogni chiamata a Heapify è eseguita si un sottoalbero di altezza inferiore all’albero completo
ogni chiamata a Heapify impiegherà, quindi, tempo limitato superiormente dalla funzione log2n.

Possiamo quindi concludere che T(n) = O(n log₂n ).

Tempo di esecuzione di CostruisciHeap (segue)

Un’analisi più attenta ci permette di ottenere un limite asintotico più stretto e preciso.
Possimo, infatti, osservare che chimate diverse a Heapify da parte di CostruisciHeap sono effettuate su sottoalberi diversi, molti dei quali hanno altezze differenti e notevolmente inferiori a quella dell’albero completo.
In altre parole, l’analisi effettuata è basata su un’approssimazione piuttosto grossolana.
Notiamo, infatti, che la maggior parte delle chiamate a Heapify sono effettuate su sottoalberi radicati sui padri delle foglie, che hanno altezza 1. Il numero di tali sottoalberi è circa n/4 (la metà delle foglie).
Analogamente, n/8 chiamate a Heapify sono effettuate su sottoalberi radicati sui padri dei padri delle foglie, che hanno altezza 2.
In generale avremo che Costruisci-Heap chiama Heapify:

n/4 volte su Heap di altezza 1
n/8 volte su Heap di altezza 2
n/16 volte su Heap di altezza 2
…
n/2^h+1 volte su Heap di altezza h

Tempo di esecuzione di CostruisciHeap (segue)

Ricordando che il tempo di esecuzione di Heapify è al più lineare sull’altenzza dell’albero di cui è chiamato, possiamo quindi affermare che:

$T(n) = \sum_{i=1}^{\lfloor log_{2}n\rfloor}\frac{n}{2^{i+1}}O(i) = O\left(\frac{n}{2} \sum_{i=1}^{\lfloor log_{2}n\rfloor}\left(\frac{1}{2}\right)^{i}i \right)$

Ricordando che:

$\sum_{i=1}^{1} \left(x\right)^{i}i \leq \sum_{i=1}^{k} \left(x\right)^{i}i \leq \sum_{i=1}^{\infty}\left(x\right)^{i}i$

E che, quando $0 < x < 1$ , $\sum_{i=1}^{\infty}\left(x\right)^{i}i$ converge alla quantità costante $\frac{x}{(1-x)^2}$ , possimo quindi concludere che:

$T(n) = O\left(\frac{n}{2} \sum_{i=1}^{\lfloor log_{2}n\rfloor}\left(\frac{1}{2}\right)^{i}i \right) = O\left(\frac{n}{2} \frac{\frac{1}{2}}{\left(1-\frac{1}{2}\right)^2}\right)= O\left(n\right)$

Poiché almeno n/2 operazioni elementari vengono effettuate per l’esecuzione della testa del ciclo for, otteniamo che $T(n) = \Theta(n)$ .

L’algoritmo di HeapSort

L’algoritmo HeapSort è una variante di SelectSort in cui la ricerca dell’elemento massimo è facilitata dal mantenimento della sequenza in uno Heap:

si costruisce uno Heap a partire dall’array non ordinato in input;
viene sfruttata la proprietà degli Heap per cui la radice A[1] dello Heap è sempre il massimo.

L’algoritmo procede scorrendo tutte le posizioni dell’array a partire dall’ultima e ad ogni iterazione:

la radice A[1] viene scambiata con l’elemento nell’ultima posizione corrente dello Heap;
viene ridotta la dimensione dello Heap e
viene ripristinato lo Heap chiamando Heapify sulla radice A[1].

L’algoritmo di HeapSort (segue)

Illustrazione grafica del funzoinamento di HeapSort.

L’algoritmo di HeapSort(segue)

Di seguito riportiamo l’algoritmo
HeapSort(A) ....CostruisciHeap(A) ...FOR i = length[A] DOWNTO 2 ........DO /* elemento massimo in A[1] */ ........."scambia A[1] e A[i]" ........./* ripristina lo heap */ .........heapsize[A] = heapsize[A]-1 .........Heapify(A,1)
È facile individuare la somiglianza con l’algoritmo SelectionSort riportato qui di seguito:
SelectSort(A) ....FOR i = length[A] DOWNTO 2 ......DO max = Findmax(A,i) ........."scambia A[max] e A[i]"
Come si può intuire, la chiamata di HeapSort a CostruisciHeap corrisponde alla prima chiamata di SelectSort a Findmax, mentre ciascuna chiamata a Heapify corrisponde ad una qualche chiamata a Findmax, esculsa la prima.

Esempio di applicazione di HeapSort

Simulazione di un'esecuzione di HeapSort.

Tempo di esecuzione di HeapSort

Per quel che riguarda l’analisi del tempo di esecuzione, possiamo osservare che HeapSort chiama, nel caso peggiore,

una volta CostruisciHeap;
n-1 volte Heapify sull’intero Heap.

Avremo quindi che:
T(n) = max(O(n), (n-1) · max(O(1), T(Heapify)))
……..= max(O(n), max(O(n), O(n · log2n)))
Concludiamo quindi che:
T(n) = O(n · log₂n)

Analisi del tempo di esecuzione di HeapSort.

Le lezioni del Corso

1. Analisi di algoritmi

2. Algoritmi di Ordinamento: InsertionSort e analisi per casi

3. Analisi di algoritmi ricorsivi

4. L'algoritmo di ordinamento HeapSort I

5. L'algoritmo di ordinamento HeapSort II