import java.util.*;

public class MyBinaryHeap implements MyPriorityQueue {

    private Comparable[] heap;
    private int size;         
  
    public MyBinaryHeap() {
        heap = new Comparable[1];
        size = 0;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    public void add(Comparable item) {
        if (size == heap.length) {
            Comparable[] newHeap = new Comparable[2 * heap.length];
            System.arraycopy(heap, 0, newHeap, 0, heap.length);
            heap = newHeap;
        }
        int parent, child = size++;
        while (child > 0 && heap[parent = (child - 1) / 2].compareTo(item) < 0) {
            heap[child] = heap[parent];
            child = parent;
        }
        heap[child] = item;
    }
  
    /* private method to demote an item from heap[parent] to its
     * proper place in a heap, assuming both left and right sub-trees
     * are properly ordered heaps */
    private static void demote(Comparable[] heap, int size, int parent) {
        Comparable item = heap[parent];
        int child; 
        while ((child = (2 * parent) + 1) < size) {
            // if there are two children, compare them
            if (child + 1 < size && heap[child].compareTo(heap[child + 1]) < 0) {
                ++child;
            }
            // compare item with the larger
            if (item.compareTo(heap[child]) < 0) {
                heap[parent] = heap[child];
                parent = child;
            } else {
                break;
            }
        }
        heap[parent] = item;
    }

    public Comparable remove() {
        if (size == 0) {
            throw new NoSuchElementException();
        }
        Comparable result = heap[0];
        heap[0] = heap[--size];
        demote(heap, size, 0);
        return result;
    }

    public void delete(Comparable item) {
        // put your code here
    }

    /*
      public Enumeration elements() {
      // put your code here
      }
    */

}