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

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.

Operazioni sugli heap[modifica | modifica wikitesto]

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.

Descrizione dell'algoritmo[modifica | modifica wikitesto]

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})}$.

Variante di Floyd[modifica | modifica wikitesto]

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.

Altri progetti[modifica | modifica wikitesto]

• Wikimedia Commons contiene immagini o altri file sull'heapsort

Collegamenti esterni[modifica | modifica wikitesto]

• (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 Wikipedia che trattano di informatica