HEAPSORT ALGORITHME DE TRI EN O(N LOG N)

// HeapSort: version optimisée

template <class T>
class HpSort {
   T* a;
   T x;
   void HS (unsigned);
   void Arrange (unsigned, unsigned);
public:
   HpSort (T _a[], unsigned n): a(_a) {if (n) HS(n);}
};

template <class T>
void Tri (T a[], unsigned n) {
   HpSort<T> X(a, n);
}

template <class T>
void HpSort<T>::Arrange (unsigned i, unsigned n) {
   unsigned j;
// x = a[i];
   while ((j = 2*i+1) < n) {
      if (j+1 < n && a[j] < a[j+1]) ++j;
      if (x >= a[j]) break;
      a[i] = a[j]; i = j;
   }
   a[i] = x;
}

template <class T>
void HpSort<T>::HS (unsigned n) { // n>0 !
   for (unsigned i = n/2; i; --i) {x = a[i-1]; Arrange(i-1, n);}
   while (--n) {
      x = a[n]; a[n] = a[0]; a[0] = x;
      Arrange(0, n);
   }
}