L’HeapSort è un algoritmo di ordinamento basato sui confronti, molto efficente. Complessità computazionale al più O(nlog_2n), al pari di QuickSort e MergeSort.

L’algoritmo si compone di 3 funzioni essenzialmente:
– La prima Rendi_heap, riceve in ingresso: l’array a[], la sua dimensione n, un certo valore lh (lunghezza heap) ed un indice i (che è l’indice da cui vogliamo partire per rendere tale nodo un heap).
– La seconda Costruisci_heap, che si occupa di richiamare sulla prima metà di array la funzione rendi_heap, per far assumere a tutto l’array la caratteristica di uno heap (Un heap è la condizione in cui i figli sx e dx sono minori o uguali al padre).
– Infine vi è l’HeapSort che concilia queste 2 funzioni in modo che l’array alla fine della sua esecuzione risulti ordinato.

Qui di seguito l’algoritmo scritto in C.

Definiamo la struttura:

//Lavoriamo su una struttura di questo tipo:
typedef struct{
int chiave, attributo;
} t_id_tab;

Funzione Rendi_Heap:

void Rendi_Heap(t_id_tab a[], int n, int lh, int i){
int s, d, max;
t_id_tab temp;
 
s = 2*i + 1;
d = 2*i + 2;
 
if ((s < lh) && (a[s].chiave > a[i].chiave))
max = s;
else
max = i;
 
if ((d < lh) && (a[d].chaive > a[max].chiave))
max = d;
 
if (max != i){
temp = a[i];
a[i] = a[max];
a[max] = temp;
Rendi_Heap(a, n, lh, max);
}
 
}

Funzione Costruisci_Heap:

//Rende Heap, tutto l'array. la funzione parte dall'indice n/2 - 1 poichè se partisse più avanti, la funzione Rendì_heap sforerebbe a destra in cerca di figli sx (s) e dx (d) 
void Costruisci_Heap(t_id_tab a[], int n, int lh){
int i;
for(i = n/2 - 1; i >= 0; i--)
  Rendi_Heap(a, n, lh, i);
 
}

Funzione HeapSort:

void HeapSort(t_id_tab a[], int n){
int i;
t_id_tab temp;
int lh = n; //inizialmente tutto l'array è ancora da trattare.
 
Costruisci_Heap(a, n, lh);
 
for(i = n-1; i > 0; i--){
temp = a[i];
a[i] = a[0];
a[0] = temp;
lh--;
Rendi_Heap(a, n, lh, 0);
}
 
}