# 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.