Home

Federica EU

1/21

Massimo Benerecetti » 4.L'algoritmo di ordinamento HeapSort I

SelectionSort: intuizione

L’algorimo SelectionSort scandisce tutti gli elementi dell’array a partire dall’ultimo elemento fino all’inizio e ad ogni iterazione esegue i seguenti passi:

Viene cercato l’elemento massimo nella parte di array che precede l’elemento corrente;
L’elemento massimo viene scambiato con l’elemento nell’ultima posizione della parte non ordinata dell’array.
Funzionamento di SelectionSort: il massimo valore della sequenza non ordinata viene scambiato con l’elemento nell’ultima posizione i corrente.

Funzionamento di SelectionSort: il massimo valore della sequenza non ordinata viene scambiato con l'elemento nell'ultima posizione i corrente.

L’algoritmo di SelectionSort

Input: una sequenza di numeri.
Output: una permutazione (riordinamento) tale che tra ogni coppia di elementi adiacenti nella sequenza valga “qualche” relazione di ordinamento (ad es. ≤).

L’algoritmo di SelectionSort è definito come segue:

Selection-Sort(A)

FOR i = length[A] DOWNTO 2 DO

max = Findmax(A,i) "scambia A[max]con A[i]"

Findmax(A,x)

max = 1 FOR i = 2 to x DO

IF A[max] < A[i] THEN

max = i

return max

SelectionSort: tempo di esecuzione

È facile osservare che, utilizzando le tecniche di calcolo del tempo di esecuzione, il tempo impiegato dalla funzione Findmax(A,x) è proporzionale al numero di elementi tra l’indice 1 e l’indice x.
Infatti, il numero di esecuzioni della testa ciclo for è pari a x e ogni esecuzione del corpo del ciclo for impiega tempo costante.
Ne segue che ogni chiamata a Findmax(A,x) impiega tempo $\Theta(x).$
L’algoritmo Selection-Sort(A), eseguito su un array di n elementi, effettua n esecuzioni della testa del ciclo for. Ogni esecuzione del corpo effettua una chiamata Findmax(A,i) che impiega tempo $\Theta(i)$ e uno scambio tra i valori di due posizioni dell’array, che impiega tempo costante.
Il tempo complessivo è dato, quindi, dalla formula $\sum_{i=2}^{n}(\Theta(i) + \Theta(1)) = \Theta(n^2)$ .

HeapSort: intuizione

L’algoritmo HeapSort:

è una variante di SelectionSort in cui la ricerca dell’elemento massimo è facilitata dall’utilizzo di una opportuna struttura dati;
la struttura dati è chiamata heap;
lo heap è una variante della struttura dati albero binario;
in uno heap si può accedere all’elemento massimo in tempo costante;
si può ricostruire la struttura heap in tempo sublineare.

Come vedremo, ogni operazione di ricostruzione di heap corrisponde ad una nuova ricerca del massimo.
In altre parole, HeapSort l’utilizzo della struttura dati heap garantisce che le ricerche del massimo possano essere effettuate in tempo sublineare.

Alberi Binari

Un albero binario è una struttura dati astratta definita come un insieme finito di nodi che:

è vuoto oppure
è composto da tre insiemi disgiunti di nodi:

un nodo radice;
un albero binario detto sottoalbero sinistro;
un albero binario detto sottoalbero destro.

Struttura di un Albero Binario.

Alberi Binari (segue)

Applicazione della definizione di albero binario ai due sottoalbero destro e sinistro della radice.

Alberi Binari (segue)

Sviluppo completo della definizione di albero binario nel sottoalbero sinistro della radice.

Alberi Binari (segue)

Archi, nodi figli e nodi padre in un albero binario.

Alberi Binari (segue)

Un nodo di un albero binario si dice nodo foglia (o solo foglia) se non ha figli (cioè se entrambi i sottoalberi di cui è radice sono vuoti).

Un nodo si dice nodo interno se ha almeno un figlio.

Un percorso dal nodo i al nodo j è la sequenza di archi che devono essere attraversati per raggiungere il nodo j dal nodo i.

Nodi interni, foglie e percorsi in un Albero Binario.

Alberi Binari (segue)

In un albero binario la profondità di un nodo è la lunghezza del percorso dalla radice al nodo (cioè il numero di archi tra la radice e il nodo).

La profondità massima di un nodo all’interno di un albero è l’altezza dell’albero.

Il grado di un nodo è il numero di figli di quel nodo.

Altezza dell'albero, profondità e grado dei nodi di un Albero Binario.

Albero Binario Pieno

Un albero binario si dice pieno se:

tutte le foglie hanno tutte la stessa profondità h;
tutti i nodi interni hanno grado 2.
Un albero binario pieno di altezza h ha esattamente $2^{h+1} - 1$ nodi.
Un albero binario pieno con n nodi ha altezza esattamente $\lfloor log_{2} n\rfloor$ .

Altezza e numero dei nodi di un Albero Binario pieno.

Albero Binario Completo

Un albero binario si dice completo se:

tutte le foglie hanno profondità h o h-1, dove h è l’altezza dell’albero;
tutti i nodi interni hanno grado 2, eccetto al più uno.

Dalla definizione si evince che un albero binario pieno di altezza h è il più grande albero binario completo della stessa altezza h.

Un albero binario completo di altezza h ha, quindi, un numero di nodi n tale che 2^h ≤ n ≤ 2^h+1-1;
Un albero binario completo con n nodi ha altezza esattamente $\lfloor log_{2} n\rfloor$ (come un albero binario pieno).

Albero Binario Completo.

Albero Heap

Un Albero Heap è un albero binario completo tale che per ogni nodo i: entrambi i nodi j e k figli di i hanno valore non maggiore (cioè, ≤) di i.

Uno Heap rappresenta un ordiamento parziale, infatti:

tra un figlio e suo padre vale sempre una relazione di ordinamento (cioè, padre ≤ figlio);
ma tra i figli di uno stesso padre non è garantita valere alcuna particolare relazione di ordinamento.

Esempio di Albero Heap (i valori associati ai nodi sono riportati in nero all'interno dei nodi).

Albero Heap come ordinamento parziale.

Array e Alberi Binari Completi

Ogni array A può essere visto come uno Albero Binario Completo in cui:

la radice dello Heap contiene l’elemento in prima posizione dell’array (cioè, A[1]);
se il nodo j dello Heap contiene l’elemento in posizione i dell’array (cioè, A[i]):
- il figlio sinistro di j contiene l’elemento in posizione 2i dell’array (cioè, A[2i]);
- il figlio destro di j contiene l’elemento in posizione 2i+1 dell’array (cioè, A[2i+1]).

Ne consegue che i nodi interni dell’albero completo contengono la prima metà dei elementi dell’array, mentre le foglie contengono la seconda metà degli elementi.

Array e Alberi Binari Completi (segue)

Le seguenti funzioni implementano la corrispondenza tra array e albero binario completo:
SINISTRO(i)

return 2i

DESTRO(i)

return 2i+1

PADRE(i)

return |i/2|

Array e Alberi Binari Completi (segue)

Corrispondenza tra Array di elementi e Albero Binario Completo.

Albero Completo e Array (segue)

Corrispondenza tra indici di un Array di elementi e nodi del corrispondente Albero Binario Completo.

Array Heap

Data la corrispondenza tra albero completo e array, possimo ora definire la nozione di array heap.
Un Albero Heap è un albero binario completo tale che per ogni nodo i: entrambi i entrambi i suoi nodi figli j e k hanno valore non maggiore del valore di i.

Un array A è uno Heap se:

A[i ] ≥ A[2i ] e A[i] ≥ A[2i+1]

Si noti che nei due esempi precedenti sia l’albero completo che l’array sono anche degli Heap.

Heapify: intuizione

Heapify(A,i): è l’operazione che ripristina la proprietà di Heap al (sotto)albero radicato in i, assumendo che i suoi sottoalberi sinistro e destro siano già degli Heap.
Heapify(A,i): dati due Heap H₁ e H₂ con radici SINISTRO(i) e DESTRO(i) e un elemento v in posizione i:

se lo Heap H, con radice A[i] = v, vìola la proprietà di Heap (cioè se A[i] < A[SINISTRO(i)] o A[i] < A[DESTRO(i)]) allora:

scambia A[i] con la più grande tra le radici degli Heap H₁ e H₂ e
applica Heapify ricorsivamente al sottoalbero modificato, con radice SINISTRO(i) o DESTRO(i).

Si noti che uno dei due sottoalberi rimane invariato, quindi è certamente uno Heap al termine dell’operazione.

Applicazione di Heapify: situazione iniziale.

Applicazione di Heapify al sottoalbero sinistro se v < x e y ≤ x.

Algoritmo Heapify

Di seguito è riportato lo pseudocodice dell’algoritmo Heapify:

Heapify(A,i)
l = SINISTRO (i) r = DESTRO(i) IF l⇐heapsize[A] AND A[l] > A[i]
THEN maggiore = l ELSE maggiore = i
IF r ⇐ heapsize[A] AND A[r] > A[maggiore]
THEN maggiore = r
IF maggiore ⇐ i
THEN "scambia A[i] e A[maggiore]"
Heapify(A,maggiore)
La variabile heapsize[A] denota la dimensione corrente (numero di elementi) dello Heap.
Il controllo l ≤ heapsize[A] (r ≤ heapsize[A]) verifica, quindi, che l’elemento in posizione l (r rispettivamente) sia effettivamente contenuto all’interno allo Heap.

Heapify: esempio di applicazione

Esempio di applicazione di Heapify.

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