public class HeapSort {

   private static void swap (int [] data, int i, int j) {
      final int temp = data[i];
      data[i]=data[j];
      data[j]=temp;
   }

   public static void heap_sort (int [] data, int n) {
      makeHeap (data, n);
      
      printArray (data, n);
      for (int i=n-1; i>0; i--) {
	 swap (data, 0, i);   // data[0] is max
	 System.out.print (i+": ");
	 printArray (data, n);
	 reheapDown (data, i-1);
      }
   }
      
   private static void makeHeap (int [] data, int n) {
      for (int i=1; i<n; i++) {
	 reheapUp (data, i);
      }
   }

   private static int leftSubtree (int i)  { return 2*i+1; }
   private static int rightSubtree (int i) { return 2*i+2; }
   private static int parent (int i)       { return (i-1)/2; }  // int division
   /*
   private boolean hasLeftSubtree (int i)  { return 2*i+1 < size; }
   private boolean hasRightSubtree (int i) { return 2*i+2 < size; }
   */

   // Return the index of the root node's child with the larger key.
   // Precondition:  root must be the index of an interior node
   private static int largerChild (int [] data, int root, int size) {
      final int leftChild  = leftSubtree (root);
      final int rightChild = rightSubtree (root);
      if (rightChild < size && data[rightChild]>data[leftChild]) {
	 return rightChild;
      } else {
	 // Either no right subtree or left child is bigger
         return leftChild;
      }
   }

   // Assuming that the root of the heap is the only element out of
   // place, restore the heap property:  data[Parent] >= data[Child]
   // O(log n)
   private static void reheapDown (final int [] data, int size) {
      int root = 0;
      while (2*root+1<size) {
	 // Root is an interior node
         final int maxChild = largerChild (data, root, size);
	 final int r = data[root];
	 final int max = data[maxChild];

	 if (r>=max) break;
	 // swap
	 data[root] = max;
	 data[maxChild] = r;
         root = maxChild;
      }
   }

   // Assuming that the last leaf of the heap is the only element out of
   // place, restore the heap property:  data[Parent] >= data[Child]
   // O(log n)
   private static void reheapUp (final int[] data, int bottom) {
      while (bottom > 0) {
	 final int parent = parent (bottom);
	 final int b = data[bottom];
	 final int p = data[parent];
	 if (p>=b) break;
	 // swap
	 data[bottom] = p;
	 data[parent] = b;
         bottom = parent;
      }
   }

   private static void printArray (int [] data, int n) {
      printArray (data, 0, n);
   }

   private static void printArray (int [] data, int first, int n) {
      System.out.print ("[");
      for (int i=first; i<first+n; i++) {
	 System.out.print (data[i]);
	 if (i<first+n-1) System.out.print (", ");
      }
      System.out.println ("]");
   }

   public static void main (String [] args) {
      int [] data  = new int [1000];
      int n = 0;
      for (int i=0; i<args.length; i++) {
	 data[n++] = Integer.parseInt(args[i]);
      }
      printArray (data, n);
      heap_sort (data, n);
      printArray (data, n);
   }
}