#include"stdio.h"    // printf
#include"stdlib.h"   // malloc, free & exit
typedef int elem;
typedef struct { int nMax, n; elem *t;} tas;

void creeTas(tas *a, int nMax)
{ a->nMax=nMax;
  a->n=0;
  a->t= malloc(sizeof(elem)*nMax);
}

void supprimeTas(tas *a)
{ free(a->t);
  a->t=0;
  a->nMax=0;
  a->n=0;
}

#define t(i) a->t[(i)-1]
void monteTas(tas *a, int i)
{ elem x=t(i);
  for(;;)
  { int j=i/2;          // père de i
    if(j==0) break;     // pas de père
    if(t(j)>=x) break;
    t(i)=t(j);
    t(i=j)=x;
  }
}

void descendTas (tas *a, int i)
{ elem x=t(i);
  for(;;)
  { int j=i*2;                      // fils gauche de i
    if(j>a->n) break;               // pas de fils  
    if(j<a->n && t(j+1)>t(j)) j++;  // plus grand fils
    if(t(j)<=x) break;
    t(i)=t(j);
    t(i=j)=x;
  }  
}

void insereTas (tas *a, elem x)
{ if(a->n==a->nMax) printf(" Le tas déborde.\n"), exit(1);
  t(++a->n)=x;
  monteTas(a,a->n);
}

elem oteMaxTas(tas *a)
{ elem x=t(1);
  t(1)=t(a->n--);
  descendTas(a,1);
  return x; 
}
#undef t

void arrangeTas1(tas *a)  // en O(n ln n)
{ int i;
  for(i=1;i<=a->n;i++) monteTas(a,i);
}

void arrangeTas2(tas *a)  // en O(n)
{ int i;
  for(i=a->n/2;i;i--) descendTas(a,i);
}

void triTas2 (elem *t, int n)  // prend 2 fois plus de place et de temps que triTas
{ tas a;
  creeTas(&a,n);
  int i;
  for(i=0;i<n;i++) insereTas(&a,t[i]);
  for(i=n;i;) t[--i]=oteMaxTas(&a);
  supprimeTas(&a);
}

void triTas (elem *t, int n)
{ tas a = {n,n,t};
  arrangeTas2(&a);
  int i;
  while((i=a.n)) t[i-1]=oteMaxTas(&a);
}

void afft(int *t,int n)
{ for(;n;n--) printf("%d ",*t++);
  printf("\n");
}

int main()
{ int n=11, t[n], i, x=1;
  for(i=0;i<n;i++) t[i]=x=x*5%16+1;
  afft(t,n);
  triTas(t,n);
  afft(t,n);
  return 0;
}