/* a heap of integers */

class iheap
{
    int[] A; // internal array to represent heap tree
    int size;  // number of elements in heap, != A.length
    iheap(int l) { A = new int[l+1]; size = 0; }

    int left(int n) { return n*2; }
    int right(int n) { return (n*2)+1; }
    int parent(int n) { return n/2; }  // parent==0 means n is root

    // remember that first element is A[1]; A[size] is last element

    // inserting into heap
    public void insert(int x)
    {   int temp; // for swapping
	if (size>A.length-2) return;
	size++;
	// first put the new element at the "end" of the heap
	A[size] = x;

	// now propagate upwards until it is less than parent
	int i = size; // index of last element
	while (i>1 && A[parent(i)]<A[i])
	    {
		int p = parent(i);
		temp = A[i];
		A[i] = A[p];
		A[p] = temp;
		i = p;
	    } // while
    } // insert

    // delete always deletes from top - deletes the largest element
    // returns largest element;
    public int delete()
    {
	if (size<1) return 0x80000000; // return smallest 32bit int as default
	int answer = A[1];  // value always at root.
	// take element at end of heap and place it at the root.
	A[1] = A[size]; size--;

	// propagate downwards until heap property satisfied.
	boolean stop = false;
	int i = 1; // initial position 
	int r, l, p, temp;
	while (!stop)
	    { 
		r = right(i);  l = left(i);
		if (l>size) // i is already at leaf node
		    { stop = true; }
		else if (A[i]>A[l] && (r>size || A[i]>A[r])) 
		    {stop = true; }  // already satisfy heap property.
		else
		{
		    // swap with greater of children
		    p = l; 
		    if (r<=size && A[r]>A[l]) p = r;
		    temp = A[i];
		    A[i] = A[p];
		    A[p] = temp;
		    i = p;
		}
	    } // while
	return answer;
    }  //delete

    // print the heap level by level
    public void print()
    {
	int level = 1;
	int i = 1;
	int n =0;

	int ls; // number of levels:
	ls = (int)Math.ceil(Math.log(size+1)/Math.log(2));
	while (level<=ls)
	    {
		n = (int)Math.pow(2,level-1);
		for(int j=0;j<n&&i<=size;j++)
		    {
			System.out.print(A[i++]+"\t");
		    }
		System.out.println();
		level++;
	    } // while
	System.out.println("------------");
    } //print

} // class iheap

public class intheap
{
    public static void main(String[] args)
    {
	iheap H = new iheap(100);
	H.insert(7);
	H.insert(4);
	H.insert(6);
	H.insert(9);
	H.insert(2);
	H.insert(8);
	H.print();
	System.out.println("element deleted: "+H.delete());
	System.out.println("element deleted: "+H.delete());
	System.out.println("element deleted: "+H.delete());
	H.print();

	// boxing/unboxing tests:
	Integer X = 3;
	Integer Y = 4;
	if (X.compareTo(Y)<0) System.out.println("ok");
	String A = "ab";
	String B = "abc";
	if (A.compareTo(B)<0) System.out.println("ok too");
    }
}