//
//  File:  heap.h
//
//  Sorts by building a max heap, then continually removing the
//  maximum remaining element to its proper place and reducing the
//  size of the heap.
//
//  There is one important note about this code.  Since the array A
//  starts at 0 instead of the usual 1 for a heap, the children of
//  each heap node i are in locations 2i+1 and 2i+2 and the last
//  non-leaf value is in location floor(N/2)-1. 

template <class T>
void
Percolate_Down( T A[], int i,  int N )
{
  int child;
  T tmp = A[ i ];

  for( ; i*2+1 < N; i = child ) {
    child = i*2+1;
    if ( child != N-1 && A[ child+1 ] > A[ child ] ) child++;
    if( tmp < A[ child ] )
      A[ i ] = A[ child ];
    else
      break;
  }
  A[ i ] = tmp;
}


template <class T>
void
Heap_Sort( T A[],  int N )
{
  int i;
  for( i = N/2-1; i >= 0; i-- )   // Build_Heap.
    Percolate_Down( A, i, N );

  for( i = N-1; i >= 1; i-- ) {
    Swap( A[ 0 ], A[ i ] ); // Delete_Max.
    Percolate_Down( A, 0, i );
  }
}