import cs1.Keyboard;    // EWU-specific:  keyboard input methods
import java.io.*;                 // for the output file
import java.text.DecimalFormat;   // 3-digit precision for output

/**
 *  Exercise the heap sort algorithm

 *  @author  Timothy Rolfe

 *  Just exercising code, so everything is static or local.
 */

public class HeapSort
{
// Correct the heap from parent downwards
   static void downHeap(Comparable[] heap, int parent, int n)
   {  Comparable hold = heap[parent];
      int child = 2*parent + 1;

      while (child < n)      // I.e, while still in the active heap
      {  if ( (child+1) < n && (heap[child].compareTo(heap[child+1]) < 0) )
            child++;
         if ( !(heap[child].compareTo(hold) > 0))// if NOT out of place
            break;
         heap[parent] = heap[child];
         parent = child;
         child = 2*parent + 1;
      }
      heap[parent] = hold;
   }
/**
 * Entry point for heap sort
 */
   static void heapSort (Comparable a[], int n)
   {// Sort a[0:n-1] using merge sort.
      for (int top = n / 2; top >= 0; top--)  // Heapify pass
      {  downHeap(a, top, n); }
      for (int lim = n-1; lim > 0; lim--)     // Sorting pass
      {  Comparable temp = a[lim];
         a[lim] = a[0];
         a[0] = temp;
         downHeap (a, 0, lim);
      }
   } // end heapSort
} // end HeapArray class