#include <stdio.h>
#include <stdlib.h>
#include "stddvd.h"

#define DIM 15

void heapsort(int*, int);
void siftdown(int*, int, int);
int min(int*, int, int);
void print(int*, int);

int main()
{
/* vettore già strutturato come heap! */
   int heap[DIM] = {5,23,20,29,26,21,22,35,40,50,51,34,78,59,72};

   heapsort(heap, DIM);

   print(heap, DIM);

   return 0;
}



void heapsort(int x[], int dim)
{
   int i,
       dimension = dim;

   while(dim > 1)
   {
      swap(&x[0],&x[dim-1]);

      siftdown(x, dim - 1, 0);

      dim--;
   }
}



void siftdown(int x[], int dim, int i)
{
   int c = (2 * i) + 1;

/* figlio sinistro ok */
   if(c < dim)
   {
/* figlio destro ok: seleziono figlio minore */
      if(c + 1 < dim)
         c = min(x, c, c + 1);

/* scambio se nodo deve scendere nell'heap */
      if(x[i] > x[c])
      {
         swap(&x[i],&x[c]);
         siftdown(x, dim, c);
      }
   }
}



int min(int x[], int i, int j)
{
   return ((x[i] < x[j]) ? i : j);
}



void print(int x[], int dim)
{
   int i;

   printf("\nVETTORE: ");

   for(i = 0; i < dim; i++)
      printf("%d ",x[i]);

   printf("\n");
}