/*  In this version of a polymorphic heap structure,
    The array that implements the heap is created outside of the class,
    when the instance of the class is created.  This restriction is
    due to the fact that one cannot create an array of unknown type.
*/
//package Dasearch;

public class heap<Ty extends Comparable<Ty>>
{
    Ty[] A; // internal array to represent heap tree
    int size;  // number of elements in heap, != A.length
    heap(Ty[] B) { A = B; 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

    // method to seach for an element in the heap (O(n)): returns pointer
    public Ty search(Ty x)
    {
	for(int i=1;i<=size;i++) 
	    if (A[i].equals(x)) return A[i];
	return null;
    }

    // inserting into heap
    public void insert(Ty x)
    {   Ty 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)].compareTo(A[i])<0)
	    {
		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 Ty delete()
    {
	if (size<1) return null; // return null as default
	Ty 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;
	Ty lval = null;
	Ty rval = null;
	Ty temp;
	while (!stop)
	    { 
		r = right(i);  l = left(i);
		// check if node is leaf
		if (l>size) {stop = true;} 
		else
		    if (A[i].compareTo(A[l])>=0 && (r>size || (A[i].compareTo(A[r])>=0))) {stop = true;}
		else
		{
		    // swap with greater of childeren
		    p = l;
		    if (r<=size && A[l].compareTo(A[r])<0) 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;
	while (i<=size)
	    {
		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 heap<Ty>