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

struct table
/* Pointeur vers un tableau d'entiers et taille du tableau */
{
   int *tableau;
   int taille;
};

typedef struct table Table;

Table *ALLOUER_TABLE(int longueur, int longueur_allouee)
/* Retourne un pointeur vers une Table de taille longueur_allouee, allouée dynamiquement */
/* Seules les longueur premières positions seront reconnues...*/
{
   if(longueur>longueur_allouee)
   {
      printf("Erreur d'allocation de longueurs!\n");
      return NULL;
   }
   Table *ptrtable;
   ptrtable=(Table*)malloc(sizeof(Table));
   ptrtable->tableau=(int*)malloc(longueur_allouee*sizeof(int));
   ptrtable->taille=longueur;
   return ptrtable;
}

void AFFECTER_TABLE(Table *ptrtable)
/* Lorsque la table est affectée, demande d'entrer le nombre convenable de valeurs */
{
   int i, valeur;
   if(ptrtable==NULL) return;
   printf("entrez %d valeurs.\n", ptrtable->taille);
   for(i=0;i<ptrtable->taille;i++)
   {
      printf("valeur suivante? ");
      scanf("%d",&valeur);
      ptrtable->tableau[i]=valeur;
   }
}

void AFFICHER_TABLE(Table *ptrtable)
/* Affiche le contenu du champ tableau de la table */
{
   int i;
   if(ptrtable==NULL) return;
   for(i=0;i<ptrtable->taille;i++) printf("%d ",ptrtable->tableau[i]);
   printf("\n");
}

void ECHANGER(Table *ptrtable, int i, int j)
/* Echange les éléments d'indice i et j du tableau */
{
   int tempo;
   int longueur;
   if(ptrtable==NULL) return;
   longueur=ptrtable->taille;
   if((i>=longueur)||(j>=longueur)) return;
   tempo=ptrtable->tableau[i];
   ptrtable->tableau[i]=ptrtable->tableau[j];
   ptrtable->tableau[j]=tempo;
}

void ECHANGE_DESCENDANT(Table *ptrtable, int i)
/* Rétablit la condition APO à partir du noeud d'indice i vers les feuilles */
{
   int fils, n;
   if(ptrtable==NULL) return;
   n=ptrtable->taille;
   fils=2*i+1;
   if(fils>=n) return;
   if((fils<n-1)&&(ptrtable->tableau[fils]<ptrtable->tableau[fils+1])) fils=fils+1;
   if(ptrtable->tableau[i]<ptrtable->tableau[fils])
   {
      ECHANGER(ptrtable,i,fils);
      ECHANGE_DESCENDANT(ptrtable, fils);
   }
}

void ECHANGE_MONTANT(Table *ptrtable, int i)
/* Rétablit la condition APO à partir du noeud d'indice i vers la racine */
{
   int pere;
   if(ptrtable==NULL) return;
   if(i==0) return;
   pere=(i-1)/2;
   if(ptrtable->tableau[i]>ptrtable->tableau[pere])
   {
      ECHANGER(ptrtable,pere,i);
      ECHANGE_MONTANT(ptrtable, pere);
   }
}

void INSERER(Table *ptrtable, int k)
/* Insere une nouvelle étiquette dans un tas déjà existante */
/* ATTENTION : la taille allouée à la table doit être suffisante, sinon??? */
{
   if(ptrtable==NULL) return;
   ptrtable->tableau[ptrtable->taille]=k;
   ptrtable->taille++;
   ECHANGE_MONTANT(ptrtable, ptrtable->taille-1);
}



void FABRIQUER_TAS(Table *ptrtable)
/* Transforme sur place un tableau en tas par succession d'échanges descendants */
{
   int i;
   if(ptrtable==NULL) return;
   for(i=(ptrtable->taille)/2-1;i>=0;i--) ECHANGE_DESCENDANT(ptrtable, i);
}

void EXTRAIRE_RACINE(Table *ptrtable)
/* Extrait la racine du tas, la place en dernier et reconstitue un tas de taille plus petite */
{
   if(ptrtable==NULL) return;
   if (ptrtable->taille>1)
   {
      ECHANGER(ptrtable, 0, ptrtable->taille-1);
      ptrtable->taille--;
      ECHANGE_DESCENDANT(ptrtable,0);
   }
}

void TRIE_TAS(Table *ptrtable)
/* Réalise le tri sur place d'un tableau qui est déjà constitué en tas */
{
   int i, n;
   if(ptrtable==NULL) return;
   n=ptrtable->taille;
   for(i=1;i<n;i++)
   {
      ECHANGER(ptrtable, 0, ptrtable->taille-1);
      ptrtable->taille--;
      ECHANGE_DESCENDANT(ptrtable,0);
   }
   ptrtable->taille=n;
}

int main(void)
{
   Table *a;
   int n,k;
   printf("Taille de la table ? ");
   scanf("%d",&n);
   a=ALLOUER_TABLE(n,n);
   AFFECTER_TABLE(a);
   printf("Table a:\n");
   AFFICHER_TABLE(a);
   FABRIQUER_TAS(a);
   AFFICHER_TABLE(a);
   TRIE_TAS(a);
   AFFICHER_TABLE(a);
}