Heap sort
Da Wikipedia, l'enciclopedia libera.
L' heapsort è un algoritmo di ordinamento iterativo proposto da Williams nel 1964, che dimostra quanto possa essere utile fare affidamento su strutture dati ausiliarie.
L' heapsort per eseguire l'ordinamento, fa infatti affidamento su una struttura chiamata heap (mucchio); un heap è rappresentabile con un albero binario in cui tutti i nodi seguono una data proprietà che ora vedremo.
In uno heap decrescente (utilizzato per ordinare ad esempio un array in senso crescente) ogni nodo padre contiene un valore (se parliamo di numeri, ad esempio interi) maggiore o uguale a quello dei suoi due figli diretti; e quindi sarà maggiore anche di tutti i nodi che si trovano nel sottoalbero di cui esso è la radice; notiamo che questo non implica affatto che nodi a profondità maggiore contengano valori minori di quelli a profondità minore.
Quindi in ogni istante, in un heap decrescente, la radice contiene il valore maggiore.
Questa struttura è molto usata, in particolare, per l'ordinamento di array.
In questo caso si considera come radice l'elemento iniziale; inoltre i figli di un nodo con indice j, avranno indice rispettivamente 2j, quello sinistro, 2j+1 quello destro.
Per comprendere meglio il funzionamento dell'algoritmo è bene capire che gli elementi che si trovano nella seconda metà dell'array rappresenteranno foglie dello heap e quindi esse saranno già al loro posto giusto; non vi è infatti alcun elemento dopo di esse.
L'algoritmo che ordina in senso crescente utilizzando un heap decrescente funziona così:
- si costruisce l'heap sull'array risistemando gli elementi
- si copia la radice (primo elemento) in fondo all'array (eseguendo uno scambio di elementi)
- ora si riesegue l'algoritmo considerano un array di dimensione dim-1 (questo poiché l'ultimo elemento è di sicuro il massimo del sottoarray considerato)
Notiamo subito che questo algoritmo utilizza una procedura ricorsiva.
Si può dimostrare che la sua complessità asintotica massima è 
.
Per array di piccole dimensioni è meglio l'insertion sort (
), mentre per array quasi ordinati o ordinati al contrario è meglio merge sort ().
