public class Prog4
/* step 4 removes init() from Heap1 so that Heap1
 * is completely general
 * uses compareTo 
 *constructing the heap from
 * the initial array
 */
 
{  
	final static int MAX = 7;
   public static void main(String[] as)
   {  
      Character[] x = new Character[MAX+1];
      init(x);
      Heap1 heap = new Heap1(x, MAX);
      heap.print(); 
      System.out.println("the array heapified");
      heap.build();
      heap.print(); 
   }
   
    public static void init(Character[] x)
 	{
 		char ch;
 		for(int j = 1 ; j <= MAX; j++)
 		{
 			ch = (char)('a' + j-1);
 			x[j] = new Character(ch);
 		}
    }
}
   
 class Heap1
 {
 	final int MAX;
 	Comparable[] x;
 	
 	public Heap1(Comparable[] y, int MAX)
 	{
 		x = y;
 		this.MAX = MAX;
 	}
 
 	public void build()
 	{
 		for(int j = MAX/2; j >=1; j--)
 		{
 			shiftDown(j);
 		}
 	}
 	
     public void shiftDown(int parent)
     {
	 boolean done = false;
	 int child = parent*2;
	 while(!done && child <= MAX)
	     {
		 if(child < MAX  && x[child].compareTo(x[child +1])<0 )
		     {
			 child++;
		     }
		 if(x[child].compareTo(x[parent])> 0)
		     {
			 swap(child);
		     }
		 else done = true;
		 parent = child;
		 child = 2* child;
	     }
     }

 	public void swap(int child)
 	{
 		int parent = child/2;
 		Comparable temp = x[child];
 		x[child] = x[parent];
 		x[parent] = temp;
 	}
 		
 	public void print()
 	{
 		for(int j = 1; j <= MAX; j++)
 		{
 			System.out.print(x[j]);
 		}
 	    System.out.println();
 	}
 }