Recursive implementation of Heap sort algorithm

L' heapsort è un algoritmo di ordinamento iterativo ed in-place proposto da Williams nel 1964, che si basa su strutture dati ausiliarie.

L' heapsort per eseguire l'ordinamento, utilizza una struttura chiamata heap (mucchio); un 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 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 un heap decrescente, la radice contiene il valore maggiore.

Questa struttura è molto usata, in particolare, per l'ordinamento di array.

In questo caso si considera come radice l'elemento iniziale di indice 1; inoltre i figli di un nodo con indice j, avranno indice rispettivamente 2j, quello sinistro, 2j+1 quello destro.

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.

...tratto da wikipedia

Implementazione Ricorsiva di Heap Sort

#include <stdio.h>

#define MAX 20

int sinistro(int i)
{
 return 2*i+1;
}

int destro(int i)
{
 return 2*i+2;
}

int padre(int i)
{
 return (int)(i-1/2);
}

stampavettore(int *vettore,int n)
{
 int i;

 for(i=0 ; i<=n ; printf("%d ",vettore[i++]));
}

int riempivettore(int *vettore)
{
 int i;

 i=0;
 do {
 printf("inserire l'elemento %d dell'array('-1' per terminare): ",i+1);
 scanf("%d",vettore+i);
 } while (vettore[i++] != -1);
 return i-2;
}

void scambia(int *n1,int *n2)
{
 int temp;

 temp = *n1;
 *n1 = *n2;
 *n2 = temp;
}

void heapify(int *vettore, int i,int heapsize)
{
 int l,r,maggiore;

 l = sinistro(i);
 r = destro(i);

 if ((l <= heapsize) && (vettore[l] > vettore[i]))
 {
 maggiore = l;
 }
 else
 {
 maggiore = i;
 }

 if ((r <= heapsize) && (vettore[r]>vettore[maggiore]))
 {
 maggiore = r;
 }
 if (maggiore != i)
 {
 scambia(&vettore[i],&vettore[maggiore]);
 heapify(vettore,maggiore,heapsize);
 }
}

void buildheap(int *vettore,int heapsize,int n)
{
 int i;

 for (i=(int)(n/2) ; i>=0 ; i--)
 {
 heapify(vettore,i,heapsize);
 }
}

heapsort(int *vettore,int n)
{
 int i,heapsize;

 heapsize=n;
 buildheap(vettore,heapsize,n);
 for (i=n ; i>0 ; i--)
 {
 scambia(&vettore[0],&vettore[i]);
 heapsize--;
 heapify(vettore,0,heapsize);
 }
}

main()
{
 int vettore[MAX];
 int n; /*numero di elementi*/

 n=riempivettore(vettore);

 heapsort(vettore,n);

 stampavettore(vettore,n);
}