Heapsort
# Heapsort

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

Per eseguire l'ordinamento utilizza una struttura chiamata 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 (con le foglie sull'ultimo livello compattate a sinistra) 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 uno heap decrescente, la radice contiene il valore maggiore.

Questa struttura è molto usata, in particolare, per l'ordinamento di array.

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.

## Operazioni sugli heap

Lo heap può essere rappresentato graficamente da un array. Dato ciò può essere utile conoscere come operare sullo heap in modo da conoscere il padre e i figli di un determinato elemento di indice i.

La funzione per calcolare l'elemento padre di i è $A\left[{\frac {i}{2}}\right]$.

Per il calcolo del figlio sinistro è $2i$ e per il destro è $2i+1$.

Un MaxHeap è uno heap binario se ogni elemento soddisfa la proprietà per cui ogni elemento è minore o uguale al nodo padre.

Ovvero, dato un array A, un indice i e la lunghezza n del vettore, dove i rappresenta l'indice di ogni elemento:

$A\left[{\frac {i}{2}}\right]\geq A[i]$ per ogni $1<i\leq n$

Un MinHeap, al contrario, deve soddisfare la seguente proprietà:

$A\left[{\frac {i}{2}}\right]\leq A[i]$ per ogni $1<i\leq n$

Determinare il massimo o il minimo elemento da una di queste due strutture è immediato, infatti il primo elemento $A[1]$ è sempre il massimo o il minimo dello heap, a seconda della proprietà che si è utilizzata.

## Descrizione dell'algoritmo

Concettualmente, l'algoritmo funziona nel seguente modo:

* Si costruisce un array contenente $n$ elementi da ordinare
* Si verifica che $a[i]<a[j]$ per $i>j$ e si effettua uno scambio di elementi; altrimenti si continua per $i=i+1$
* Il massimo viene scambiato con l'elemento in posizione $i$, per $i=n-1$
* Si ripete il precedente passo per $i=i-1$

Si può dimostrare che la complessità asintotica massima dello 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à, nel caso peggiore, di $O(n^{2})$.

## Variante di Floyd

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

