public class heap7
//final version
//cleaner code
//uses sequential letters. Sort done in O(nlogn) shifting 1 element
{ final static int MAX = 7;
  
  static char[] x;
 
  public static  void initialize( char[] x)
  { for( char letter = 'a'; letter <= 'g'; letter++)
  	  x[letter-'a'] = letter;
  }
  
  public static void write(char[] x, int min, int n)
  { for(int j = min; j < n; j++)
  	  System.out.print( x[j]);
	System.out.println();
  }
  
  public static void swop(char[] x, int child)
  {  int parent = child /2;
     char temp = x[child];
	 x[child]    = x[parent];
	 x[parent] = temp;
  }
  
  public static void buildHeap(char[] x)
  {  for(int j = MAX/2; j >= 1; j--)
  	   shiftDown(x, j);
  }
  
  public static void shiftDown(char[] x, int m)
  {//reheapifies heap, only node out of order is the root
   //pre: x[2..MAX] is a heap
   //post x[1..MAX] is a heap
    int parent, child;
    parent = 1;
	child = 2*parent;
	boolean done = false;
	while ( !done && child <= m)//quit at last geneation
	{ if( child < m && x[child+1] > x[child])//two children
	       child = child + 1;//larger node is left child
	 if ( x[child] > x[parent])
	 { swop(x, child);
	   parent = child;
	   child = 2*parent;
	 } 
	 else 
	    done = true;	
    }
	write(x, 1, MAX+1);
  }
		 
  public static void shift(char[] x, int m)	
  {//makes 0th element 1st element
    for(int j = m; j > 0; j--)
	  x[j] = x[j-1];
  }	 

  
  public static void sort(char[] x)
  {  //switches root with last element then reheapifies
     //subscript of last element is MAX -1
	 for(int n = MAX; n>= 2; n--)
	 {  char temp = x[1];
	 	x[1] = x[n];
		x[n] = temp;
		shiftDown( x, n - 1);				
	 } 
  }
  
  public static void main(String[] as)
  {  x = new char[MAX+1];//one more element for shift
     initialize( x);
	 write(x, 0, MAX);
	 shift(x, MAX);
	 write(x, 1, MAX + 1);
	 buildHeap(x);
	 System.out.println("heapified list");
	 write(x, 1, MAX+1);
	 System.out.println("sorted list");
	 sort(x);
	 write(x, 1, MAX+1);
  }
}