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.
 */

class HeapDemo
{
   static File   f = null;
   static PrintWriter fOut = null;

   static int[] linePos = new int[64];
   static int   usedDisplay;

// Correct the heap from parent downwards
   static void downHeap(char[] heap, int parent, int n)
   {  char 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] < heap[child+1]) )
            child++;
         if ( !(heap[child] > hold) )         // 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 (char[] 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);
         fOut.println ("After downHeap(" + top + ")");
         display(a, n);
      }
      for (int lim = n-1; lim > 0; lim--)     // Sorting pass
      {  char temp = a[lim];
         a[lim] = a[0];
         a[0] = temp;
         downHeap (a, 0, lim);
         fOut.println ("After removing " + a[lim]);
         display (a, n);
      }
   } // end heapSort

/**
 * Determine the line position on display as a complete binary tree
 */
   static public void places(int k, int n)
   {  if ( k == 0 )
         usedDisplay = 0;
      if ( k < n )
      {  places(k*2+1, n);
         linePos[k] = usedDisplay;
         usedDisplay += 2;
         places(k*2+2, n);
      }
   }

/**
 * Somewhat prettified display:  Subheap roots are directly
 * above their respective subheaps.  Good for up to about 40
 * heap entries before line-wrap causes a problem.
 */
   static public void display (char[] heap, int n)
   {  int idx,
          endIt = 2;

      fOut.print ("Current char. array: ");
      for ( idx = 0; idx < n; idx++ )
         fOut.print ( " " + heap[idx]);
      fOut.println('\n');
/* Disabled --- only needed once.
   // In-order traversal, setting into linePos where each of
   // the heap entries will print on its line.
      places(0, n);    // Pass the subscript of the root.
*/
      usedDisplay = 0;  // static data member
      for (idx = 0; idx < n; idx++)
      {
         if (idx == endIt-1) // Go to new line
         {  fOut.println ();
            usedDisplay = 0;      // Restart positions used
            endIt <<= 1;   // Next power of two.
         }
      // ?Need to space over?
         for ( ; usedDisplay < linePos[idx] ; usedDisplay++ )
            fOut.print (" ");

         fOut.print ( " " + heap[idx]);
         usedDisplay += 2;
      }
      fOut.println ('\n');
   }

/**
 * Driving main to exercise the algorithm and compare with utility method.
 */
   public static void main ( String [] args )
   {
      String testString="ASORTINGEXAMPLE";  // Text to be sorted
      char[] test=testString.toCharArray(); // As an array of char
      int    size = test.length;

      try
      {  f = new File("HeapDemo.txt");
         fOut = new PrintWriter(new FileWriter(f, true)); // append
      }
      catch (IOException e)
      {  System.err.println ("File output error:  " + e );
         System.exit(-1);
      }
   // Compute placement in the pretty-print
      places(0, size);  // Pass the subscript of the root.
      display (test, size);
      heapSort (test, size);
      fOut.close();
   }

} // end HeapDemo class