// heap of doubles, largest on top.
public class dheap
{
    double[] H;
    int size = 0; // dynamic size, not the same as max size.
    int maxsize;  // maximum size (H.length-1)
    dheap(int m)  // constructor
    {
	maxsize = m;
	H = new double[m+1];  // H[0] not used.
    }

    // size is also index of last element in heap.

    int parent(int i) { return i/2; } // root has 0 as parent.
    int left(int i) { return i*2;}
    int right(int i) { return i*2+1; }

    // insert
    public void insert(double x) throws Exception
    {
	if (size==maxsize) throw new Exception("heap full");
	size++;
	H[size] = x;  // first insert at end of heap
	// now propagate upwards:
	int i = size; // "pointer" to nodes, but is really just an index
	boolean stop = false; // controls while loop
	while (!stop)
	    {
		int p = parent(i);
		if (p>0 && H[p]<H[i])
		    { // swap with parent
			double t = H[p];
			H[p] = H[i];
			H[i] = t;
			i = p; // move upwards until root.
		    }
		else stop = true; // already ok (in place or at root)
	    }//while
    }//insert

    // delete the top of the heap (largest element)
    public double deletemax() throws Exception
    {
	if (size<=0) throw new Exception("empty heap");
	double ret = H[1]; // root value to be returned;
	H[1] = H[size]; // move last element to top of heap;
	size--;
	// now propagate downwards:
	boolean stop = false;
	int i = 1; // "pointer" to nodes, start at root.
	while (!stop)
	    {
		int l = left(i);
		int r = right(i);
		if (l>size) stop = true; // no left, so no right either
		else // at least left child exists
		{
  		  // now determine who to swap with, if any, need to swap
		  // with the larger of the two childeren
		  int c = i; // c will contain largest among i, left and right
		  if (H[l]>H[c]) c = l;
		  if (r<=size && H[r]>H[c]) c = r;
		  if (c!=i) // swap  
		    {
			double p = H[c];
			H[c] = H[i];
			H[i] = p;
			i = c; // move downwards
		    }
		  else stop = true; // node not smaller than childeren.
		}// at least left child exists.
	    }// while
	return ret;
    }//deletemax

    // print for debugging:, prints underlining array
    public String toString()
    {
	String s = "";
	for (int i=1;i<=size;i++) s = s + H[i] + " ";
	return s;
    }

    // print the heap level by level
    public void printheap()
    {
	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(H[i++]+"\t");
		    }
		System.out.println(); // new line
		level++;
	    } // while
	System.out.println("------------");
    } //print

    // but what about search???

    /* test
    public static void main(String[] args)  //test
    {
      try
      {
	dheap PH = new dheap(1024);
	PH.insert(8);
	PH.insert(6);
	PH.insert(9); PH.insert(7);
	System.out.println(PH);
	double x = PH.deletemax();
	//	System.out.println(PH);
	PH.printheap();
      } catch (Exception e) {System.out.println(e);}
    }//main
    */
}//dheap