/*
 *
 * Burton Rosenberg
 * 24 May 2002
 * 10 Sept 2003
 *
 * HeapSort
 *
 * Copyright (c) 2003, 2002 Burton Rosenberg
 * All rights reserved.
 */

/*
   Implementation which follows closely CLR Algorithms book.
   Array elements are stored in 1..n, with location 0 for
   the length of the array.
*/


public class HeapSort {

  final static int [] THE_ARRAY = { 0, 7, 6, 10, 8, 9, 4, 3, 5, 1, 2 } ;

  public static
  void main ( String [] args )
  {
     System.out.println("How to read the tree picture:\n"
                       +"\n     n"
                       +"\n     +---left_child(n)"
                       +"\n     |   +---left_child(left_child(n))"
                       +"\n     |   |"
                       +"\n     |   +---right_child(left_child(n))"
                       +"\n     |"
                       +"\n     +---right_child(n)" ) ;
     heapSort(THE_ARRAY) ;
  }

  static
  void heapSort(int [] h)
  {
        h[0] = h.length-1 ;
        heapify(h) ;
        while ( h[0]>0 )
        {
          System.out.println("After deleteMin removes "+deleteMin(h)) ;
          printArrayAsTree(h) ;
          printArray(h) ;
        }
  }

  static
  void heapify( int [] h )
  {
     System.out.println("\nOriginal tree:") ;
     printArrayAsTree(h) ;
     printArray(h) ;
     for ( int i=parent(h[0]); i>0; i-- )
     {
        System.out.println("After heapify at node with value "+h[i]) ;
        downheap( h, i ) ;
        printArrayAsTree(h) ;
        printArray(h) ;
     }
  }

  static
  int deleteMin( int [] h )
  {
     int r = h[1] ;
     swap( h, 1, h[0] ) ;
     h[0] -- ;
     downheap(h, 1) ;
     return r ;
  }

  static
  void downheap( int [] h, int i )
  {
     if ( rc(i)<=h[0]
          && h[rc(i)]<=h[lc(i)]
          && h[rc(i)] < h[i] )
    {
       swap( h, i, rc(i) ) ;
       downheap( h, rc(i) ) ;
    }
    else if ( lc(i)<=h[0]
              && h[lc(i)]<h[i] )
    {
       swap( h, i, lc(i) ) ;
       downheap( h, lc(i) ) ;
    }
  }

  static
  int lc( int i ) { return 2*i ; }

  static
  int rc( int i ) { return 2*i+1 ; }

  static
  int parent( int i ) { return i/2 ; }

  static
  void swap ( int [] h, int i, int j )
  {
      int t = h[i] ;
      h[i] = h[j] ;
      h[j] = t ;
  }

  static
  void printArrayAsTree( int [] h )
  {
      System.out.println() ;
      if ( h[0]==0 ) System.out.print(EMPTY) ;
      else printArrayAsTreeAux( h, 1, "", "" ) ;
      System.out.println() ;
  }

  static
  void printArrayAsTreeAux( int [] h, int n, String useOnce, String useAfter )
  {
      if ( n<=h[0] )
      {
         System.out.println( useOnce + h[n] ) ;
         if ( lc(n)>h[0] )
         {
            System.out.println( useAfter );
         }
         else
         {
            printArrayAsTreeAux( h, lc(n), useAfter+L_ONCE, useAfter+L_AFTER ) ;
            printArrayAsTreeAux( h, rc(n), useAfter+R_ONCE, useAfter+R_AFTER ) ;
         }
      }
      else
         System.out.println( useOnce ) ;
  }

  static final String L_ONCE = "+---" ;
  static final String L_AFTER= "|   " ;
  static final String R_ONCE = "+---" ;
  static final String R_AFTER= "    " ;
  static final String EMPTY = "Tree empty\n" ;

  static 
  void printArray( int [] h ) {
      System.out.print("Array (and length): [") ;
      for (int i=0; i<h.length; i++ )
         System.out.print(h[i]+" ") ;
      System.out.println("]\n\n") ;
  }

}