/*********************************************************
  TD d'Algorithmique IN102
  ENSTA

  Implementation des tas et heapsort
  
                                                       GP
*********************************************************/

// Exercices 1 et 2 : voir poly
// ----------------------------

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

// un tas est défini par le nombre n d'éléments, le nombre
// maximal d'éléments (max) et un tableau t de max éléments 
struct tas
{
  int n;
  int max;
  int *t;
};

typedef struct tas Tas;

// initialisation d'un tas (notamment allocation du tableau t)
void initTas(int nb, Tas *T)
{
  (*T).t=(int *)malloc(sizeof(int)*nb);
  (*T).max=nb;
  (*T).n=0;
}

void erreur(int x)
{
  printf("Erreur (%d)\n",x);
  exit(x);
}

// échange du contenu de 2 variables
void swap(int *a, int *b)
{
  int t;
  t=*a;
  *a=*b;
  *b=t;
}

// impression (infixée) d'un tas
void imprime(Tas T)
{
  int i;
  for(i=0;i<T.n;i++)
    printf("%d ",T.t[i]);
  printf("\n");
}

// impression d'un tas (vaguement sous forme d'arbre)
void imprimearbre(Tas T)
{
  int i,j,k;
  j=0;
  k=1;
  for(i=0;i<T.n;i++)
    {
      printf("%02d ",T.t[i]);
      if (i==j)
	{
	  printf("\n");
	  k*=2;
	  j+=k;
	}
    }
  printf("\n\n");
}
	  

// recherche (triviale) du maximum d'un tas
int maximum(Tas T)
{
  if (T.n==0)
    erreur(-1);
  return T.t[0];
}

// insertion d'un élément dans un tas
void insere(int v, Tas *T)
{
  int i=(*T).n;
  if (i==(*T).max)
    erreur(-2);
  (*T).t[i]=v;
  while ((i>0) && ((*T).t[i]>(*T).t[(i-1)/2]))
    {
      swap(&((*T).t[i]),&((*T).t[(i-1)/2]));
      i=(i-1)/2;
    }
  (*T).n++;
}

// suppression du maximum d'un tas
void supprime(Tas *T)
{
  int i,cont;
  
  if ((*T).n==0)
    erreur(-3);
  (*T).n--;
  (*T).t[0]=(*T).t[(*T).n];
  i=0;
  do
    {
      cont=0;
      if (2*i+2<(*T).n)
	{
	  if (((*T).t[2*i+1]>(*T).t[2*i+2])&&((*T).t[i]<(*T).t[2*i+1]))
	    {
	      swap(&((*T).t[i]),&((*T).t[2*i+1]));
	      cont=1;
	      i=2*i+1;
	    }
	  else
	    if (((*T).t[2*i+1]<(*T).t[2*i+2])&&((*T).t[i]<(*T).t[2*i+2]))
	      {
		swap(&((*T).t[i]),&((*T).t[2*i+2]));
		cont=1;
		i=2*i+2;
	      }
	}
      else
	if (2*i+1<(*T).n)
	  if ((*T).t[i]<(*T).t[2*i+1])
	    {
	      swap(&((*T).t[i]),&((*T).t[2*i+1]));
	      cont=1;
	      i=2*i+1;
	    }
    }
  while (cont);
} 

/*********************************************************
  Tri par tas (Heapsort)

  Exercice 5
  ----------
  Complexité du tri par tas:
  1/ insertion des n éléments : n*O(log(n))
  2/ répéter n fois
      recherche du maximum : O(1)
      suppression du maximum : O(log(n))

  Au final, on obtient une complexité en O(n.log(n))
  en moyenne et dans la pire cas.
*********************************************************/

void heapsort(int *tab, int nb)
{
  Tas T;
  int i;
  
  initTas(nb,&T);
  for(i=0;i<nb;i++)
    insere(tab[i],&T);
  for(i=nb-1;i>=0;i--)
    {
      tab[i]=maximum(T);
      supprime(&T);
    }
  free(T.t);
}

// affichage d'un tableau
void printtab(int *A, int nb)
{
  int i;
  for(i=0;i<nb;i++)
    printf("%d ",A[i]);
  printf("\n");
}

// initialisation vaguement aléatoire d'un tableau
void inittab(int *A, int nb)
{
  int i;
  for(i=0;i<nb;i++)
    A[i]=rand() % 100;
}

// programme principal de test
int main(int argc, char * argv[])
{
  Tas T;
  int i;
  int tab[10];
  
  printf("Ajout de 10 valeurs aléatoires dans un tas\n");
  initTas(10,&T);
  for(i=0;i<10;i++)
    {
      insere(rand()%100,&T);
      imprime(T);
    }
  printf("\n");
  printf("Impression du tas sous forme d'arbre\n");
  imprimearbre(T);

  printf("Suppression du maximum dans un tas\n");
  for(i=0;i<10;i++)
    {
      supprime(&T);
      imprime(T);
    }

  // Démonstration de heapsort
  
  printf("Démonstration du tri par tas (heapsort)\n");
  inittab(tab,10);
  printtab(tab,10);
  heapsort(tab,10);
  printtab(tab,10);
  exit(0);
}
/********************************************************/