title: Heapsort
text: # 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.
  
  