import java.io.IOException;

class Heap{
    
    private final static void swap(char[] a, int i, int k){
        char temp = a[i];
        a[i] = a[k];
        a[k] = temp;
        }

     static char[] upHeap(char[] ap, char ext){
				int l = ap.length + 1;
				char[] a= new char[l];
				System.arraycopy(ap, 0, a, 0, l-1);
				int i = l-1;
				a[i] = ext;
				while (i > 0){
					int ni = (i-1)/2;
					if (a[i] > a[ni]){
						swap(a, i, ni);
						i = ni;
						}
					else break;
					}
				return a;
			}

     
		static char[] downHeap(char[] ap){
				int l = ap.length - 1;
				char[] a = new char[l];
				System.arraycopy(ap, 1, a, 1, l-1);
				a[0] = ap[l];
				int i = 0;
				int ni = 1;
				while (ni < l){    // Linker oder rechter Zweig
					if (((ni+1) < l) && (a[ni] < a[ni+1])) ni++; 
					if (a[i] < a[ni]){ // tauschen ?
						swap(a, i, ni);
						i = ni;
						ni += ni + 1;
						}
					else break;
				}
				return a;
			} 
    

  }

public class HeapT {

    public static void main(String args[]) {
     String bsp1 = "WSPFGAMDBC";
     String bsp2 = "WSPFGAMDBCE";
     char [] feld;
     System.out.println("HeapTester - UpHeap");
     System.out.println("");
     System.out.println(bsp1);
     feld = Heap.upHeap(bsp1.toCharArray(),'T');
     System.out.println(feld);
     System.out.println("");
     System.out.println("HeapTester - DownHeap");
     System.out.println("");
     System.out.println(bsp2);
     feld = Heap.downHeap(bsp2.toCharArray());
     System.out.println(feld);
    }
}