#include <stdio.h> 
#include <stdlib.h>
typedef int element;
typedef struct {int n, n_max; element *t;} tas;  // 0 <= n <= n_max    element t[n_max]  

void creer_tas(tas *a, int nmax)
{ a->n=0;
  a->n_max=nmax;
  a->t=malloc(nmax*sizeof(element)); // réserve la place du tableau
}

void detruire_tas(tas*a)
{ free(a->t); // Seule cette instruction est indispensable
  a->t=0;     // Donc a->t[i] provoquera une erreur de segmentation.
  a->n=0;     // Le tas est vide
  a->n_max=0;
}

#define n    a->n
#define t(k) a->t[(k)-1] // fonctionne à condition que tous nos arguments s'appellent "a"

void monte(tas *a, int i)   // i est la position de l'élément à faire monter dans le tas
{ while(i>1 && t(i/2)<t(i)) // tant que t(i) a un père et que ce père est plus petit
  { element aux=t(i);       //   on échange t(i) et son père t(i/2)
    t(i)=t(i/2);
    t(i=i/2)=aux;           //   l'élément est monté de t(i) à t(i/2), mais doit peut-être encore monter
  }
} // temps de calcul: O(log(i))

void descendre(tas *a, int i) // on échange l'élément avec le plus grand de ses 2 fils
{ for(;;)
  { int j=2*i;
    if(j>n) return ;       // 2i est trop grand : Il n'y a pas de fils.
    if(j+1<=n && t(j+1)>t(j)) j++; // L'autre fils t(2*i+1) existe et est plus grand.
    if(t(i)>=t(j)) return; // t(i) est bien plus grand que son plus grand fils : Il est à sa place.
    element aux=t(i);
    t(i)=t(j);
    t(i=j)=aux;            //   l'élément est descendu de t(i) à t(j), mais doit peut-être encore descendre
  }
}//temps de calcul: O(log(n)-log(i)) car log(n) est la longueur des branches et
//  log(i) la profondeur de l'élément dont on part :
// Si on monte, on monte au plus de log(i) et si on descend, on descend au plus de log(n)-log(i) = log(n/i) 

void ajout(tas *a, element x)
{ t(++n)=x;
  monte(a,n);
}

element enleve_sommet(tas *a)
{ element x=t(1);
  t(1)=t(n--);
  descendre(a,1);
  return x;
}

void arrange1(tas *a)
{ int i;
  for(i=1;i<=n;i++) monte(a,i);
}//temps de calcul de cette procedure: n log(n) car monte(a,i) est en log(i)<=log(n)
// Plus précisément : somme pour i=1 à n de log(i)
// qui vaut à peu près : intégrale pour x dans [1,n] de log(x)dx
// qui est la variation de x log(x)-x entre 1 et n
// c(est-à-dire n log(n) -n

void arrange2(tas *a)
{ int i;
  for(i=n;i>0;i--) descendre(a,i);
} // Le temps de calcul de cette procédure est la somme pour i=1 à n de log(n/i)
// C'est  n log(n) - somme pour i=1 à n de log(i)    =  n log(n) - (n log(n) -n))  =n
// cette fonction est bien plus efficace que la précédente

#undef t
#undef n

void tritas1(element t[], int n)
{ tas a;
  int i;
  creer_tas(&a,n);
  for(i=0;i<n;i++) ajout(&a,t[i]);            // somme de 1 à n de log(i) = nlog(n)-n
  for(i=n-1;i>=0;i--) t[i]=enleve_sommet(&a); // somme de n à 1 de log(i) = nlog(n)-n
  detruire_tas(&a);                           // car on a fait un malloc avec creer_tas
} //complexité: temps 2(n log(n)-n) = O(n log(n))     mémoire : 2n

void tritas2(element t[], int n)
{ tas a={n,n,t};
  int i;
  arrange1(&a);                              // somme de 1 à n de log(n.i) = n
  for(i=n-1;i>0;i--) t[i]=enleve_sommet(&a); // somme de n à 1 de log(i) = nlog(n)-n
} //complexité: temps n log(n)     mémoire : n

void afft(element t[], int n)
{ int i; 
  for(i=0;i<n;i++) printf("%d ",t[i]);
  printf("\n");
}

#define n 100
int main()
{ int t[n], x=0, j;
  for(j=0;j<n;j++) t[j]=x=5*x+1; // t={1,6,31,156,...}
  afft(t,n);
  tritas1(t,n);
  afft(t,n);
  return 0;
}