#include<stdio.h>
#include<math.h>
#include<stdlib.h>

float numeros[20];

void trocaFloat(void *data1,void *data2) {
  float temp;

  temp=*(float *)data1;
  *(float *)data1=*(float *)data2;
  *(float *)data2=temp;
}

// compara dois numeros do tipo float, retornando:
//    -1 se o primeiro e menor que o segundo
//     1 se o primeiro e maior que o segundo
//     0 se os dois sao iguais
// repare que e necessaria a conversao de void * para float *, e tambem o
// uso do operador * para obter o conteudo apontado pela variavel.

int comparaFloat(void *a, void *b) {
  if (*(float *)a < *(float *)b) return -1;
  if (*(float *)a > *(float *)b) return 1;
  if (*(float *)a == *(float *)b) return 0;
}


// devolve o índice do filho esquerdo no no de indice i
int filho_esq(int i) {
  return 2*i;
}

// devolve o indice do filho direito do no de indice i
int filho_dir(int i) {
  return 2*i+1;
}

// efetua um push down no no de indice i
// parametros descritos na funcao heapSort
void pushDown( int i,void *heap,int num_eltos,int tam_tipo,int(*compFunc)(void *a,void *b),void(*trocaFunc)(void *a,void *b) ) {
  int ha_esq=0,ha_dir=0;

  if (filho_esq(i)<=num_eltos) ha_esq=1;
  if (filho_dir(i)<=num_eltos) ha_dir=1;

  if (ha_esq&&!ha_dir) {
    if (compFunc(heap+i*tam_tipo,heap+filho_esq(i)*tam_tipo)<0) {
       trocaFunc(heap+filho_esq(i)*tam_tipo,heap+i*tam_tipo);
       pushDown(filho_esq(i),heap,num_eltos,tam_tipo,compFunc,trocaFunc);
    }
  }
  else
  if (ha_esq&&ha_dir) {
    if ( (compFunc(heap+i*tam_tipo,heap+filho_esq(i)*tam_tipo)<0) ||
         (compFunc(heap+i*tam_tipo,heap+filho_dir(i)*tam_tipo)<0) ) {
      if (compFunc(heap+filho_esq(i)*tam_tipo,heap+filho_dir(i)*tam_tipo)>0) {
	trocaFunc(heap+filho_esq(i)*tam_tipo,heap+i*tam_tipo);
	i = filho_esq(i);
      }
      else {
	trocaFunc(heap+filho_dir(i)*tam_tipo,heap+i*tam_tipo);
	i = filho_dir(i);
      }
      pushDown(i,heap,num_eltos,tam_tipo,compFunc,trocaFunc);
    }
  }
}

// funcao para fazer a montagem da heap
// parametros descritos na funcao heapSort
void montaHeap(void *heap,int num_eltos,int tam_tipo,
     int(*compFunc)(void *a,void *b),void (*trocaFunc)(void *a,void *b) ) {
  int i;
  for (i=num_eltos/2;i>=1;i--) {
    pushDown(i,heap,num_eltos,tam_tipo,compFunc,trocaFunc);
  }
}

// funcao para fazer a desmontagem da heap
// parametros descritos na funcao heapSort
void desmontaHeap( void *heap,int num_eltos, int tam_tipo,
     int (*compFunc)(void *a,void *b),void (*trocaFunc)(void *a,void *b) ) {
  int i;
  int n=num_eltos;
  for (i=1;i<=n;i++) {
    trocaFunc(heap+1*tam_tipo,heap+num_eltos*tam_tipo);
    num_eltos--;
    pushDown(1,heap,num_eltos,tam_tipo,compFunc,trocaFunc);
  }
}

// heapSort: funcao que ordena uma lista dada, chamando, em ordem,
// a rotina que monta a heap e a que efetua a desmontagem
// parametros:
//   lista - ponteiro para o array a ser ordenado
//   num_eltos - numero de elementos do array
//   tam_tipo - tamanho, em bytes, de um elemento do array
//   *compFunc - ponteiro para a funcao de comparacao
//   *trocaFunc - ponteiro para a funcao que efetua a troca de dois elementos
//                no vetor
void heapSort( void *lista,int num_eltos,int tam_tipo,int (*compFunc)(void *a,void *b),void (*trocaFunc)(void *a,void *b) ) {
  montaHeap(lista,num_eltos,tam_tipo,compFunc,trocaFunc);
  desmontaHeap(lista,num_eltos,tam_tipo,compFunc,trocaFunc);
}


main() {
  int N=10;       // numero de elementos
  int i; 
//  float *numeros; // vetor que armazena os elementos
  int segundos;

//  numeros=(float*)malloc((N+1)*sizeof(float));

  // inicializa o gerador de numeros aleatorios com o relogio da maquina
  segundos=time(NULL);
  srand(segundos);

  printf ("Antes:\n");
  for (i=1;i<=N;i++) {
    // artificio para gerar numeros entre 0 e 1000
    // RAND_MAX e uma constante definida na biblioteca stdlib.h
    // e que indica o maximo valor retornado por rand()
    numeros[i]=rand()/(RAND_MAX/1000);
    printf ("%g\n",numeros[i]);
  }

  printf ("\n");

  heapSort(numeros,N,sizeof(float),comparaFloat,trocaFloat);

  printf ("Depois do heapSort:\n");
  for (i=1;i<=N;i++) {
    printf ("%g\n",numeros[i]);
  }
}