// Generic (Polymorphic) Heap.

// class that adds an additional index to determine ordering
class ordered<Ty extends Comparable<Ty>> implements Comparable<ordered<Ty>>
{
    public Ty item;
    protected int counter;
    public ordered(Ty a, int b) {item =a; counter = b;}
    public int compareTo(ordered<Ty> other)
    {
	int r = item.compareTo(other.item);
	if (r==0) 
	    return other.counter - counter;  
   	    // smaller counter gets higher priority
	else 
	    return r;
    }
}// ordered

/////////////
public class gheap<GT extends Comparable<GT>> //implements heap<GT>
{
    protected ordered<GT>[] A;   // the internal heap representation
    protected int size = 0; // size of actual heap, not same as A.length
    protected int counter = 0;  // for implementing a queue

    // indices make use of A[0] as a heap element.
    public int left(int i)
    { return (i+1)*2 - 1; }
    public int right(int i)
    { return (i+1)*2; }
    public int parent(int i) 
    { return (i+1)/2 - 1; }


    public gheap(int n)  // constructor that gives compiler warning:
    {
	A = (ordered<GT>[]) new ordered[n];
    }


    public int size() { return size; }  // public readonly access to heap size
    public int maxsize() { return A.length; } // maximum heap size

    // The insert function:
    // Algorithm is to first insert element at end of heap, then propagate up
    // The function will return true on success
    public boolean insert(GT x0)
    {
	if (size>A.length-1) return false;  // max heap size reached.

	ordered<GT> x = new ordered<GT>(x0,counter++);

	A[size] = x;  // insert at end of heap.
	// propagate upwards until either root reached, or heap property met:
	int i = size; // index of current node
	int p = parent(i);
	while (i!=0 && A[i].compareTo(A[p])>0)
	    {
		ordered<GT> temp = A[i];
		A[i] = A[p];
		A[p] = temp;
		i = p; // move upwards
		p = parent(i);
	    }
	size++;
	return true;
    }// insert

    // The deletetop function: deletes and returns element at top of heap.
    // Throws system error if heap is empty.  Algorithm is to take last
    // element of heap, place it at the top, and propagate downwards.
    public GT deletetop()
    {
	if (size==0) throw new Error("empty heap error - can't delete");
	GT answer = A[0].item; // value to be returned
	A[0] = A[--size];  // put last value at root
	int i = 0;  // current node index
	boolean stop = false;
	while (!stop)
	    {
		int left = left(i);
		int right = right(i);
		int j = -1; // candidate swap index, -1 means can't swap
		if (left<size && A[left].compareTo(A[i])>0) 
		    j = left;  // candidate found
		if (right<size && A[right].compareTo(A[i])>0 
		    && A[right].compareTo(A[left])>0) 
		    j = right; // better candidate found
		if (j != -1)
		    {
			ordered<GT> temp = A[i];
			A[i] = A[j];  A[j] = temp;
			i = j;  // move downwards
		    }
		stop = (j == -1);
	    }
	return answer;
    }//deletetop

    public GT deletemax() { return deletetop(); }  // alias for deletetop

    
    // search of x in heap, return index, -1 if not found:
    protected int find(GT x)
    {
	int ax = -1;
	for(int i=1;i<size && ax==-1;i++) if (A[i].item.compareTo(x)==0) ax = i;
	return ax;
    }

    public boolean search(GT x) { return find(x) != -1; }


    /* main is for testing. UNCOMMENT to run test only:   
    public static void main(String[] args) throws Exception
    {
	gheap<Double> H = new gheap<Double>(args.length);
	for(int i=0;i<args.length;i++) H.insert(Double.parseDouble(args[i]));
	for(int i=0;i<args.length;i++)
	    System.out.printf("%.2f ",H.deletetop());
	System.out.println();
    }
    */
}// gheap


// place this file in same directory as heap.java and other programs that
// use it.