#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#define INFINI INT_MAX /*plus grand int, valeur contenue dans limits.h*/
void construire_tas(int *,int);
void ranger_tas(int *,int);
void echanger(int *,int,int);
void afficher(int *,int);
void main ()
{
  int nbr_donnees, * tableau;
  printf("Quel nombre de données voulez-vous trier  ?  ");
  scanf("%d",&nbr_donnees);
  tableau = (int *)malloc((nbr_donnees+1)*sizeof(int));
  construire_tas(tableau,nbr_donnees);
  ranger_tas(tableau,nbr_donnees);
  afficher(tableau,nbr_donnees);
  free(tableau); 
}
void echanger(int *tableau, int ind1,int ind2)
{
  int tampon;

  tampon=tableau[ind1];
  tableau[ind1]=tableau[ind2];
  tableau[ind2]=tampon;
}
void construire_tas(int * tableau,int nbr_donnees)
{
  int i,j;

  tableau[0]=INFINI;
  printf("Entrez les données à trier :\n");
  for (i=1;i<=nbr_donnees;i++)
    {
      scanf("%d",&tableau[i]);
      j=i;
      while (tableau[j]>tableau[j/2])
	{
	  echanger(tableau,j,j/2);
	  j=j/2;
	}
    }
} 
void ranger_tas(int *tableau,int nbr_donnees)
{
  int i,j,max;   /*max contient l'indice du fils de j si j n'a qu'un fils,
		   sinon max contient l'indice du plus grand des deux fils*/

  for (i=nbr_donnees;i>1;i--)
    {
      echanger(tableau,1,i);
      j=1;
      while (2*j<=i-1)
	{
	  if (2*j==i-1) max = i-1;
	  else max = ((tableau[2*j]>tableau[2*j+1]) ? 2*j : 2*j+1);
	  if (tableau[j]>tableau[max]) break;
	  else
	    {
	      echanger(tableau,j,max);
	      j=max;
	    }
	}
    }
}
void afficher(int *tableau,int nbr_donnees)
{
  int i;

  printf("Voici vos données triées :\n");
  for (i=0;i<nbr_donnees;i++)
    printf("%4d%c",tableau[i+1],(i%5==4 ? '\n' : ' '));
}