Esercizi di programmazione in Pascal->HeapSort

HeapSort

In questo piccolo tutorial verrà spiegato l'implementazione del classico ordinamento HeapSort.
Questo algoritmo utilizza come struttura dati un Heap, per ottenere una complessità di o(nlogn).

Un Heap è una struttura dati archiviata in un Array dove gli elementi sono disposti a formare un albero binario completo. Ogni nodo dell'albero corrisponde ad un elemento dell'array che contiene il valore del nodo.

Indichiamo con "A" la variabile contente l'array, e "heap_size" la variabile contenente il numero di elementi dello heap memorizzati nell'array.
La radice dell'albero è A[1], è per ogni nodo A[i], A[i*2] corrisponde al nodo (o foglia) sinistro e A[i*2+1] corrisponde al nodo (o foglia) destro.

Heapify è l'algoritmo utilizzato per la gestione dell'heap; prende un ingresso un array A, e un indice "i" dove A[i] è un elemento che non rispetta la prorietà degli heap (A[i] può essere più piccolo dei suoi figli). L'algoritmo sposterà questo elemento in modo ricorsivo (fa scendere l'elemento nell'albero) fino a ripristinare l'heap, ovvero quando A[i] è più grande dei suoi figli.
Con la variabile "sinistra" indichiamo il nodo sinistro di "i" e con la variabile "destra" il nodo destro. La variabile "max_lunghezza" corrisponde al valore massimo tra A[i], A[sinistra] e A[destra].
Se A[i] non è il massimo valore (cioè "i" non corrisponde a "max_lunghezza") allora avviene lo scambio tra A[i] e A[max_lunghezza] e continua la ricorsione con indice "max_lunghezza". Si osservi che nel calcolare "max_lunghezza" occorre controllare che "sinistra" e "destra" corrispondano a indici validi (cioè inferiori a "heap_size").

Di seguito il codice di Heapify:
Per la costruzione dell'heap si procederà dal nodo più in basso al nodo più in alto. Si osservi che la seconda metà dell'array sono tutte foglie, quindi l'algoritmo partirà dalla metà dell'array (nodo più in basso) fino al primo nodo (nodo più in alto).

Di seguito il codice di Build_Heap:
L'algoritmo dell'HeapSort si basa sul presupposto che l'elemento più grande si trova nella radice dell'albero. Inizialmente si costruisce l'heap, quindi si estrae di volta in volta la radice dell'albero (A[1]), ed ad ogni estrazione si ripristina l'heap con Heapify (l'heap è più piccolo di un elemento).
Ad ogni estrazione l'heap contenuto nell'array diventa sempre più piccolo e la parte rimanente contiene gli elementi ordinati.
Di seguito il codice di Heapsort:
Il corpo del programma crea un vettore con numeri generati casualmente, richiama la procedura di ordinamento e quindi stampa il risultato.
Vediamo di seguito il codice.



Scarica sorgente (627 byte)