1  public class Heap<E> {
  2    private java.util.ArrayList<E> list = new java.util.ArrayList<>();
  3    private java.util.Comparator<? super E> c;
  4    
  5    /** Create a default heap using a natural order for comparison */
  6    public Heap() {
  7      this.c = (e1, e2) -> ((Comparable<E>)e1).compareTo(e2);
  8    }
  9  
 10    /** Create a heap with a specified comparator */
 11    public Heap(java.util.Comparator<E> c) {
 12      this.c = c;
 13    }
 14    
 15    /** Create a heap from an array of objects */
 16    public Heap(E[] objects) {
 17      this.c = (e1, e2) -> ((Comparable<E>)e1).compareTo(e2);
 18      for (int i = 0; i < objects.length; i++)
 19        add(objects[i]);
 20    }
 21  
 22    /** Add a new object into the heap */
 23    public void add(E newObject) {
 24      list.add(newObject); // Append to the heap
 25      int currentIndex = list.size() - 1; // The index of the last node
 26  
 27      while (currentIndex > 0) {
 28        int parentIndex = (currentIndex - 1) / 2;
 29        // Swap if the current object is greater than its parent
 30        if (c.compare(list.get(currentIndex),
 31            list.get(parentIndex)) > 0) {
 32          E temp = list.get(currentIndex);
 33          list.set(currentIndex, list.get(parentIndex));
 34          list.set(parentIndex, temp);
 35        }
 36        else
 37          break; // the tree is a heap now
 38  
 39        currentIndex = parentIndex;
 40      }
 41    }
 42  
 43    /** Remove the root from the heap */
 44    public E remove() {
 45      if (list.size() == 0) return null;
 46  
 47      E removedObject = list.get(0);
 48      list.set(0, list.get(list.size() - 1));
 49      list.remove(list.size() - 1);
 50  
 51      int currentIndex = 0;
 52      while (currentIndex < list.size()) {
 53        int leftChildIndex = 2 * currentIndex + 1;
 54        int rightChildIndex = 2 * currentIndex + 2;
 55  
 56        // Find the maximum between two children
 57        if (leftChildIndex >= list.size()) break; // The tree is a heap
 58        int maxIndex = leftChildIndex;
 59        if (rightChildIndex < list.size()) {
 60          if (c.compare(list.get(maxIndex),
 61              list.get(rightChildIndex)) < 0) {
 62            maxIndex = rightChildIndex;
 63          }
 64        }
 65  
 66        // Swap if the current node is less than the maximum
 67        if (c.compare(list.get(currentIndex), 
 68        		list.get(maxIndex)) < 0) {
 69          E temp = list.get(maxIndex);
 70          list.set(maxIndex, list.get(currentIndex));
 71          list.set(currentIndex, temp);
 72          currentIndex = maxIndex;
 73        }
 74        else
 75          break; // The tree is a heap
 76      }
 77  
 78      return removedObject;
 79    }
 80  
 81    /** Get the number of nodes in the tree */
 82    public int getSize() {
 83      return list.size();
 84    }
 85    
 86    /** Return true if heap is empty */
 87    public boolean isEmpty() {
 88      return list.size() == 0;
 89    }
 90  }