Heap sort

Da Wikipedia, l'enciclopedia libera.
Heap sort
Esecuzione dell'algoritmo. In una prima fase la lista viene riordinata per rispettare l'heap. Poi viene mostrata brevemente la struttura dati binaria e in seguito la lista viene riordinata.

Esecuzione dell'algoritmo. In una prima fase la lista viene riordinata per rispettare l'heap. Poi viene mostrata brevemente la struttura dati binaria e in seguito la lista viene riordinata.
Classe Algoritmo di ordinamento
Struttura dati Array
Caso peggiore temporalmente O(nlogn)
Caso ottimo temporalmente O(nlogn)[1]
Caso medio temporalmente \Theta(nlog n)
Caso peggiore spazialmente O(n) totale
O(1) ausiliario
Ottimale No

L'heapsort è un algoritmo di ordinamento iterativo ed in-place proposto da Williams nel 1964, che si basa su strutture dati ausiliarie.

L'heapsort per eseguire l'ordinamento, utilizza una struttura chiamata heap (mucchio); un heap è rappresentabile con un albero binario in cui tutti i nodi seguono una data proprietà, detta priorità. Esso è completo almeno fino al penultimo livello dell'albero e ad ogni nodo corrisponde uno ed un solo elemento.

In uno heap decrescente (utilizzato per ordinare ad esempio un array in senso crescente) ogni nodo padre contiene un valore maggiore o uguale a quello dei suoi due figli diretti, di conseguenza risulterà maggiore anche di tutti i nodi che si trovano nel sottoalbero di cui esso è la radice; 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 di indice 1; 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.

Heap sort[modifica | modifica wikitesto]

L'algoritmo che ordina in senso crescente inizia creando uno heap decrescente. Per ogni iterazione si copia la radice (primo elemento dell'array) in fondo all'array stesso, eseguendo uno scambio di elementi. L'algoritmo poi ricostruisce uno heap di n-1 elementi spostando verso il basso la nuova radice, e ricomincia con un altro scambio (tra il primo elemento dell'array e quello in posizione n-1), eseguendo un ciclo che considera array di dimensione progressivamente decrescente.

Si può dimostrare che la complessità asintotica massima dell'heap sort è O(n \log n). Tuttavia, in generale (e soprattutto per array quasi ordinati) altri algoritmi con la medesima complessità asintotica, per esempio quick sort o merge sort, ottengono migliori prestazioni. Per array di piccole dimensioni è addirittura più veloce l'insertion sort nonostante abbia una complessità di O(n^2).

Variante di Floyd[modifica | modifica wikitesto]

Nella costruzione della struttura heap mediante l'algoritmo heap sort, si confrontano il massimo dei figli portandoli alla radice: così si ha un risparmio sul numero di confronti da eseguire.

Altri progetti[modifica | modifica wikitesto]

informatica Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica