/* Un tas est un arbre binaire dont les sommets sont numérotés de 1 à n, le père
du sommet i étant le sommet i/2 (ou (i-1)/2 si i est impair), la racine étant le
sommet numéro 1. De plus la clef d'un sommet est toujours plus grande que la clef
de chacun de ses fils.
                          75(1)
                     /            \
                  /                   \
            60(2)                        71(3)
          /       \                    /       \
    43(4)           23(5)           53(6)        67(7)
    /   \          /    \          /
 13(8)  37(9)  22(10)   3(11)  45(12)
Ce tas est rangé sous la forme d'un tableau de 12 éléments :
75 60 71 43 23 53 67 13 37 22 3 45
*/
#include <stdio.h>
#include <stdlib.h>
typedef int element;
typedef struct{int n,nmax; element *t;} tas;
/* nmax est la place réservée pour le tableau t, c'est donc le nombre maximal
d'éléments qu'on peut mettre dans ce tas. On s'en sert uniquement pour vérifier
que le tas ne déborde pas quand on lui ajoute un élément.
n est le nombre d'éléments effectivement présents dans le tas à un instant donné.
Seules les n premières cases du tableau t sont utilisées. Les (nmax-n) dernières
sont libres, elles serviront si on rajoute des éléments dans le tas.
Les tas sont utiles quand on manipule des ensembles de nombres (ou de chaînes de
caractères ou d'éléments qui peuvent se comparer), dans lesquels on veut
 - ajouter un élément,
 - enlever un élément,
 - trouver le plus grand élément et l'enlever.
En effet, avec un tas, chacune de ces trois opérations se fait en O(log n).
Lorsqu'on part d'un tas valide et qu'on remplace un de ses éléments par un nombre
plus grand ou plus petit on peut facilement le réarranger pour le rendre de
nouveau valide : Si le nouvel élément est trop grand, on l'échange éventuellement
avec son père s'il est plus petit, puis éventuellement avec son grand-père, puis
éventuellement avec son arrière grand-père, etc..
Si le nouvel élément est trop petit, on l'échange éventuellement avec son plus
grand fils s'il est plus grand, puis éventuellement avec un de ses petits-fils,
puis éventuellement avec un de ses arrières petits-fils, etc..
procédure monte(var tas a, entier i)
   tant que i a un père j et que a.t[j]<a.t[i] faire
      échanger a.t[i] et a.t[j]
      i:=j
   fait
fin procédure monte

procédure descend(var tas a,entier i)
   tant que i a un fils plus grand que lui faire
      j:= le plus grand fils de i
      échanger a.t[i] et a.t[j]
      i:=j
   fait
fin procédure descend

monte(a,i) fait un nombre d'échanges au plus égal à la longueur du
chemin allant de la racine au sommet i, c'est-à-dire E(log2(i)).
descend(a,i) fait un nombre d'échanges au plus égal à la longueur du
plus long chemin allant du sommet i vers une feuille, c'est-à-dire E(log2(n/i)).*/
#define at(i) (a->t[(i)-1])
void monte(tas *a, int i)
{ for(;;)
  { int j=i/2;              // j:=père de i
    if(!j) break;           // i=1 pas de père
    if(at(j)>=at(i)) break; // le père est plus grand
    { element x=at(i); at(i)=at(j); at(j)=x; }
    i=j;
  }
}
void descend(tas *a, int i)
{ for(;;)
  { int j=i*2;                        // j:= le premier fils de i
    if(j>a->n) break;                 // pas de fils
    if(j<a->n && at(j+1)>at(j)) ++j;  // j est le plus grand fils
    if(at(j)<=at(i)) break;           // les fils sont plus petits
    { element x=at(i); at(i)=at(j); at(j)=x; }
    i=j;
  }
}
void modifie(tas *a, int i, element x) {at(i)=x, monte(a,i), descend(a,i);}
/* Lorsqu'on ajoute un élément à un tas on l'ajoute au bout du tableau
et on le fait remonter à sa place */
void ajoute(tas *a, element x)
{ if(a->n==a->nmax) printf("ça déborde\n"),exit(1);
  at(++a->n)=x;
  monte(a,a->n);
}
/* Lorsqu'on enlève un élément d'un tas, on bouche le trou avec le
dernier élément du tableau, qu'on fait alors monter ou descendre */
void enleve(tas *a, int i) {at(i)=at(a->n--), monte(a,i), descend(a,i);}
// Enlever le plus grand élément d'un tas c'est enlever sa racine
int enlevepg(tas *a,element *x)
{ if(!a->n) return 0;         // Le tas est vide
  *x=at(1); at(1)=at(a->n--);
  descend(a,1);
  return 1;
}
/* Pour fabriquer un tas de n éléments, on peut partir d'un tas vide
et ajouter les éléments un par un, cela prend un temps en
log(1)+log(2)+log(3)+...+log(n)=log(!n)=n log(n)-n+O(log(n))=O(n)+n log n
Mais on peut le faire en O(n) : pour cela on range d'abord les éléments
n'importe comment dans le tableau puis on fait descendre à leur place,
dans l'ordre, les éléments n, n-1, n-2, ..., 3, 2, 1.
En effet au moment où on fait descendre le sommet i, les deux
sous-arbres ayant pour racine 2i et 2i+1, ses deux fils, sont des tas.
Il suffit donc de faire descendre i à sa place pour que le sous-arbre
ayant pour racine i devienne un tas.
Le temps de calcul est en
f(n)=E(log2(n/1))+E(log2(n/2))+...+E(log2(n/n))
ln(2) f(n)<=ln(n/1)+ln(n/2)+ln(n/3)+...+ln(n/(n-2))+ln(n/(n-1))+ln(n/n)=
n ln(n)-ln(!n)=n+O(ln(n))=O(n)
On peut calculer f(n) plus précisément :
Pour i>n/2 le terme E(log2(n/i)) est nul. Donc
f(n)=E(log2(n/1))+E(log2(n/2))+...+E(log2(n/E(n/2)))
f(n)=E(n/2)+E(log2(n/2/1))+E(log2(n/2/2))+...+E(log2(n/2/E(n/2)))
f(n)=E(n/2)+f(E(n/2))
Donc f(n)=E(n/2)+E(n/4)+E(n/8)+...
     f(n)<  n/2 +  n/4 +  n/8 +...=n
En fait f(n)=n-(le nombre de bits à 1 dans l'écriture en binaire de n).
Par exemple 23=16+4+2+1 s'écrit 10111 en binaire et f(23)=23-4=19
i              1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
E(23/i)       23 11  7  5  4  3  3  2  2  2  2  1  1  1  1  1  1  1  1  1  1  1  1  
E(log2(23/i))  4  3  2  2  2  1  1  1  1  1  1  0  0  0  0  0  0  0  0  0  0  0  0
f(23)= 4+3+2+2+2+1+1+1+1+1+1=19 */
void arrange(tas *a)
{ int i;
  for(i=a->n/2;i;--i) descend(a,i);
}
/* On peut trier un tableau de n éléments en utilisant un tas.
Cela donne un tri sur place sans mémoire supplémentaire, en temps O(n log(n)) */
void heapsort2(int n,element t[n]);
void heapsort (int n,element t[n])
{ element x; tas a={n,n,t};
  arrange(&a);
  while(enlevepg(&a,&x)) t[a.n]=x;
}
void afft(element *t,int n)
{ while(n--) printf("%d ",*t++);
  printf("\n");
}
int main()
{ int i, n=20;
  element t[n],x=0;
  for(i=0;i<n;++i) t[i]=x=5*x+1;
  afft(t,n);
  heapsort2(n,t);
  afft(t,n);
  return 0;
}
/* On peut rendre la procédure heapsort plus rapide et indépendante des autres
en dévelopant tous les appels de procédure qu'elle contient. On obtient d'abord :
procédure heapsort(int n,var element t[n])
   tas a=(&t,n)
   pour i=n/2,...,2,1 faire
      descendre(a,i)
   fait
   pour a.n=n,...,3,2 faire
      échanger t[1] et t[a.n]
      descendre(a,1)
   fait
fin procédure heapsort
On peut regrouper les deux boucles pour qu'il n'y ait qu'un seul appel à descendre.
procédure heapsort(int n,var element t[n])
   tas a=(&t,n)
   i:=n/2
   tant que a.n>1 faire
      si i>0 alors
         --i
      sinon
         échanger t[1] et t[a.n]
         --a.n
      finsi
      descendre(a,i+1)
   fait
fin procédure heapsort
En développant l'appel à descendre et en remplaçant le tas a par le tableau t et
l'entier n on obtient :
procédure heapsort(int n,var element t[n])
   i:=n/2
   tant que n>1 faire
      si i>0 alors
         --i
      sinon
         échanger t[1] et t[n]
         --n
      finsi
      j=i+1
      faire indéfiniment
         jj:=2*j
         si jj>n alors quitter la boucle infinie
         si jj<n et t[jj+1]>t[jj] alors ++jj
         si t[j]>=t[jj] alors quitter la boucle infinie
         echanger t[j] et t[jj]
         j:=jj
      fait
   fait
fin procédure heapsort
L'échange de deux éléments se fait par trois affectations, mais en remarquant
qu'une des deux valeurs échangées est toujours la même et en la mettant une
fois pour toute dans la variable x, on peut remplacer l'échange par une seule
affectation.
procédure heapsort(int n,var element t[n])
   i:=n/2
   tant que n>1 faire
      si i>0 alors
         x:=t[i]
         --i
      sinon
         x:=t[n]; t[n]:=t[1]
         --n
      finsi
      j=i+1
      faire indéfiniment
         jj:=2*j
         si jj>n alors quitter la boucle infinie
         si jj<n et t[jj+1]>t[jj] alors ++jj
         si x=t[jj] alors quitter la boucle infinie
         t[j]:=t[jj]
         j:=jj
      fait
      t[j]:=x
   fait
fin procédure heapsort
En C les indices vont de 0 à n-1 et non de 1 à n : */
void heapsort2(int n,element t[n])
{ int i, j, jj;
  element x;
  for(i=n/2;n>1;)
  { if(i) x=t[--i];
    else  x=t[--n], t[n]=t[0];
    for(j=i;;j=jj)
    { jj=2*j+1;
      if(jj>=n) break;
      if(jj<n-1 && t[jj+1]>t[jj]) ++jj;
      if(x>=t[jj]) break;
      t[j]=t[jj];
    }
    t[j]=x;
  }
}