// Heap sort with linear time heap builder
// Programmer: E. Kaltofen (November 23, 1993)
#ifdef DEBUG
#include <iostream.h>
#endif
typedef int ElType; // for testing purposes

int fastheapsort(ElType A[], int n)
// sorts the array A[0],...,A[n-1] into < order
// note: one must have ElType operator<(ElType)
// returns the number of comparisions
{int i, j, k, d, comp = 0;
 ElType tmp;
#ifdef DEBUG
 int oldcomp;
#endif

 // make the heap in O(n) time
 for(k = n/2 - 1; // there are n/2 internal nodes,
                  // numbered from 0,1,...,n/2 - 1
     k >= 0; k--)
    {// make the subtree rooted in A[k] into a heap
     // its subtrees rooted in A[2*k+1] and A[2*k+2] are heaps already
     tmp = A[k];
     // demote element A[k]
     for(j = k; 2*j+1 <= n-1; // as long as children are left
         j = i) // position of demoted element
        {// find index of the larger of the children
         if ( 2*j+2 > n-1 ) // only one child
            i = 2*j+1;
         else {comp++;
               if ( A[2*j+1] < A[2*j+2] )
                  i = 2*j+2;
               else i = 2*j+1;};
         comp++;
         if (tmp < A[i])
             A[j] = A[i]; // promote child
         else break;
        }; // end for j
     A[j] = tmp;
    }

 // remove roots continuously
 for(k=n-1; k>=1; k--)
    {// at this point the elements A[k+1],...,A[n-1] are the correct elements
     // and the elements A[0],...,A[k] form a heap of the above format
     tmp = A[k];
     A[k] = A[0]; // remove the root, the largest element in A[0],...,A[k]
#ifdef DEBUG
     oldcomp = comp;
#endif
     // demote tmp from A[0] down
     for(j = 0; 2*j+1 <= k-1; // as long as children are left
         j = i) // position of demoted element
        {// find index of the larger of the children
         if ( 2*j+2 > k-1 ) // only one child
            i = 2*j+1;
         else {comp++;
               if ( A[2*j+1] < A[2*j+2] )
                  i = 2*j+2;
               else i = 2*j+1;};
         comp++;
         if (tmp < A[i])
             // promote child
             A[j] = A[i];
         else break;
        }; // end for j
     A[j] = tmp;
#ifdef DEBUG
        cout << "Demotion of element " << k << " costed " << comp-oldcomp
             << " comparisions" << endl;
#endif
      };// end for k
 return(comp);}// end fastheapsort