/*  This version uses the Comparator as well as the Comparable interface.
    It also uses "lambda expressions," which are a new feature of Java 1.8.

  Polymorphic priority heaps, largest value on top.
  Heap axiom.  The value at every node cannot be smaller than the values
  at each of its children nodes.
  Use internal array to implement heap "tree", with index 0 representing
  the root.  Given node index i, left(i)= 2*i+1 and right(i)=2*i+2, while
  parent(i) = (i-1)/2.

// we also use the Comparator in addition to the Comparable interface.
// This is the principal addition to this version.  If we wish to change
// the way objects are compared, we can use the Comparator<T> interface,
// which requires you to implement a
// int compare(T x, T y)  
// method, which is similar to the compareTo method of Comparable<T>:
// it should return 0 if x and y are "==", negative value if "x<y" and
// a positive value if "x>y".  The line in main:
//	HI.setComparator((x,y) -> y-x); // smallest on top
// switches the heap so that the smallest value is at the top.
// This line uses a new java feature (new in 1.8) call lambda expressions,
// which allows you to create an implementation of a simple interface
// much more easily.  This feature is commonly found in modern programming
// languages. It is equivalent to doing the following:
// class mycomparator<type> implements Comparator<type>
// { public int compare(type x, type y) { return y-x; } }
// ...
// HI.setComparator(new mycomparator<type>());

*/
import java.util.*;

class heap<T extends Comparable<T>>
{
  protected T[] H; // internal array representing heap.
  protected int size; // size of current heap, not same as H.length!
  public int size() { return size; } // size is read-only externally.
  public int maxsize() { return H.length; }
  public heap(T[] A)   // preferred constructor
  { H = A; size=0; 
      cmt = null;
  } 
  public heap(int m) // will cause compiler warning (ok to ignore)
  {
     H = (T[]) new Comparable[m]; // downcast from Object is OK.
     size = 0;  cmt= null;
  }

  protected int left(int i) { return 2*i+1; }
  protected int right(int i) { return 2*i+2; }
  protected int parent(int i) { return (i-1)/2; }

  // a separate comparator can be used:
  protected Comparator<T> cmt;  // default null
  public void setComparator(Comparator<T> c) 
  { cmt=c; 
  }
  
  protected boolean gt(T x, T y) // greater than
      {
	  if (cmt!=null) return cmt.compare(x,y)>0;
	  else return x.compareTo(y)>0;
      }

  // lookup heap, without delete
  public T getmax()
  { 
    if (size<1) return null; 
    return H[0];
  }

  // insert x into heap: place at end, then propagate upwards
  // returns false on failure.
  public boolean insert(T x)
  {
     if (size > H.length-1) return false;
     H[size++] = x; // place at end, inc size
     // propagate upwards
     int cur = size-1; // current position
     int p = parent(cur);
     while (cur>0 && gt(H[cur],H[p]))
     { // propagate upwards
	 T temp = H[cur];
       H[cur] = H[p];  H[p] = temp;
       cur = p;  // switch current to parent
       p = parent(cur); // recalc parent
     }//while
     return true;
  }//insert

// deletetop: take last element, move to top, propagate downwards:
  public T deletemax()
  {
     if (size<0) return null;
     T answer = H[0];
     H[0] = H[--size]; // place at top:
     // now propagate downwards.
     boolean done = false;
     int i = 0; // current position
     int c = 0; // swap candidate
     while (c != -1)
     {
	 int l = left(i);
	 int r = right(i);
	 c = -1; // swap candidate
	 if (l<size && gt(H[l],H[i])) c = l; // set candidate to left
	 if (r<size && gt(H[r],H[i]) && gt(H[r],H[l])) c=r;
	 if (c!= -1) 
	     {
		 T temp = H[i];  H[i] = H[c]; H[c] = temp;
		 i = c; 
	     }
     }//while
     return answer;
  }//deletemax

  public void drawheap() // use only with heapdisplay program
  {
      heapdisplay W = new heapdisplay(1024,768);
      W.drawtree(H,size);
  }

}//heap

public class heapsj18
{
    public static void main(String[] args)
    {
	heap<Integer> HI = new heap<Integer>(200);
	// HI.setComparator((x,y) -> x-y); // largest on top
	HI.setComparator((x,y) -> y-x); // smallest on top
	for(int i=0;i<100;i++) HI.insert((int)(Math.random()*1000));
	HI.drawheap();
	for(int i=0;i<100;i++) System.out.print(HI.deletemax() + "  ");
	System.out.println();
    }//main
}