Heapsort

Questa voce o sezione sull'argomento programmazione non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti.

Questa voce sull'argomento programmazione è solo un abbozzo.

Contribuisci a migliorarla secondo le convenzioni di Teknopedia.

Heapsort
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	${\displaystyle O(nlogn)}$
Caso ottimo temporalmente	${\displaystyle O(nlogn)}$[1]
Caso medio temporalmente	${\displaystyle O(nlogn)}$
Caso peggiore spazialmente	${\displaystyle O(n)}$ totale ${\displaystyle O(1)}$ ausiliario
Ottimale	No
Manuale

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.

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 è ${\displaystyle A\left[{\frac {i}{2}}\right]}$.

Per il calcolo del figlio sinistro è ${\displaystyle 2i}$ e per il destro è ${\displaystyle 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:

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

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

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

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

Concettualmente, l'algoritmo funziona nel seguente modo:

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

Si può dimostrare che la complessità asintotica massima dello heap sort è ${\displaystyle 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 ${\displaystyle O(n^{2})}$.

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.

• Wikimedia Commons contiene immagini o altri file sull'heapsort

• (EN) Eric W. Weisstein, Heapsort, su MathWorld, Wolfram Research.

V · D · M Algoritmi di ordinamento
Teoria	Teoria della complessità computazionale · Notazione O Grande · Array · Lista · Stack · Coda · Ordinamento comparativo · Ordinamento adattivo
Algoritmi a scambio	Bubble sort · Shaker sort · Odd-even sort · Comb sort · Gnome sort · Quicksort
Algoritmi di selezione	Selection sort · Heap sort · Smoothsort
Algoritmi ad inserimento	Insertion sort · Shell sort · Tree sort · Library sort · Patience sorting
Algoritmi a fusione	Merge sort · Timsort
Algoritmi non comparativi	Radix sort · Bucket sort · Counting sort · Pigeonhole sort
Altri algoritmi	Rete di ordinamento · Ordinamento topologico · Ordinamento bitonico · Ordinamento delle frittelle
Algoritmi inefficienti	Stupid sort · Trippel sort

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