import java.util.*;

class Heap<T extends Comparable<T>>{
    
    private T[] theHeap;
    private int maxHeapPos;
    private int nextPos;
    
    Heap(int max){
    	maxHeapPos = max;
    	nextPos=0;
    	theHeap = ( T[] ) new Comparable[max];   	
    }
    
    
    private final T getHeap(int i){ return theHeap[i];}
    
    private final void swap(int i, int k){
        T temp = theHeap[i];
        theHeap[i] = theHeap[k];
        theHeap[k] = temp;
        }

     boolean istLeer(){ return nextPos == 0;}
     
     
     void insertHeap(T ... t) throws Exception{
     	for (T el : t)insertHeap(el);
      }
      
     void insertHeap(T t) throws Exception{
     	if (nextPos==maxHeapPos) throw new Exception("Heap Full");
     	theHeap[nextPos] = t; 
     	upHeap(nextPos);
      nextPos++;
      }
      
     private void upHeap(int sohn){
				int vater = (sohn-1)/2;
				if (getHeap(vater).compareTo(getHeap(sohn)) < 0){
					 swap(vater,sohn);
					 upHeap(vater);
					}
			}
			
			T getNext(){
				if (istLeer()) return null;
				T result = getHeap(0);
				nextPos--;
				theHeap[0] = theHeap[nextPos];
				downHeap(0);
				return result;
			}

     
		private void downHeap(int vater){
				int lSohn = 2*vater+1;
				int rSohn = lSohn+1;
				if (lSohn >= nextPos) return; // keine Söhne da!
				if (rSohn == nextPos){ // nur linker Sohn da
					if (getHeap(vater).compareTo(getHeap(lSohn)) < 0)
					  swap(vater,lSohn);
					  return;
					}
				else{
						int maxSohn = (getHeap(rSohn).compareTo(getHeap(lSohn))  < 0) ? lSohn : rSohn;
						if (getHeap(maxSohn).compareTo(getHeap(vater)) < 0) return;
						else{
							swap(vater,maxSohn);
							downHeap(maxSohn);
						}
				  }
			  } 
    
    public String toString(){  
      StringBuilder sb = new StringBuilder() ;
      for (int i=0; i < nextPos;i++) sb.append(getHeap(i)+" ");
      return sb.toString();
     }	

    public static void main(String ... args) throws Exception{
     Heap<Character> myHeap = new Heap<Character>(100);
     myHeap.insertHeap('W','S','P','F','G','A','M','D','B','C');
     //myHeap.insertHeap('A', 'D','B','C','W','S','P','F','G','M');
     System.out.println(myHeap);
     myHeap.insertHeap('T');
     System.out.println(myHeap);
     
     while(!myHeap.istLeer()){
     	 System.out.println(myHeap.getNext());
     	 System.out.println(myHeap);
      }
     
    }
}