import java.util.Vector;

/**
 * A Heap.  See notes for more details.
 */
public class Heap
{
  // +--------+--------------------------------------------------
  // | Fields |
  // +--------+

  /**
   * All the elements in the heap.
   */
  Vector elements;

  /**
   * The comparator used to decide where things go.
   */
  GComparator compare;

  /**
   * The length of the heap.
   */
  int length;

  // +--------------+--------------------------------------------
  // | Constructors |
  // +--------------+

  /**
   * Create a new heap.
   */
  public Heap(GComparator compare) {
    this.compare = compare;
    this.elements = new Vector();
    this.length = 0;
  } // Heap(GComparator)


  // +---------+-------------------------------------------------
  // | Methods |
  // +---------+

  /**
   * Add a new element to the heap.
   */
  public void add(Object newElement) {
    this.elements.add(newElement);
    swapUp(this.length);
    ++this.length;
  } // add(Object newElement)

  /**
   * Delete and return the smallest element in the heap.
   */
  public Object deleteSmallest() {
    // Remember the smallest element.
    Object smallest = this.elements.get(0);
    // Shove the rightmost element into the root
    --this.length;
    this.elements.set(0, this.elements.get(this.length));
    this.elements.remove(this.length);
    // Swap the element down to the right place.
    swapDown(0);
    // Return the smallest element.
    return smallest;
  } // deleteSmallest()

  void swapDown(int pos) {
    // Case 1: No children.  Done.
    if (left(pos) >= this.length)
      return;
    // Case 2: Only one child.  Swap if necessary.
    else if (right(pos) >= this.length) {
      if (compare.mayPrecede(this.elements.get(left(pos)),
                             this.elements.get(pos))) {
        swap(pos, left(pos));
        swapDown(left(pos));
      } // Element at pos is greater than left child.
    } // Only one child
    // Case 3: Two children, the leftmost is smaller ...
    else if (compare.mayPrecede(this.elements.get(left(pos)),
                                this.elements.get(right(pos)))) {
      if (compare.mayPrecede(this.elements.get(left(pos)),
                             this.elements.get(pos))) {
        swap(pos, left(pos));
        swapDown(left(pos));
      } // Element at pos is greater than left child.
    } // two children, leftmost smaller
    // Case 4: Two children, rightmost is smaller.
    else {
      if (compare.mayPrecede(this.elements.get(right(pos)),
                             this.elements.get(pos))) {
        swap(pos, right(pos));
        swapDown(right(pos));
      } // Element at pos is greater than left child.
    } // two children, rightmost smaller
  } // swapDown

  void swapUp(int pos) {
    if (pos <= 0) return;
    if (compare.mayPrecede(this.elements.get(pos),
                           this.elements.get(parent(pos)))) {
      swap(pos, parent(pos));
      swapUp(parent(pos));
    }
  } // swapUp(int)

  /**
   * Dump the heap to the screen.
   */
  public void dump() {
    dump(0, "");
  } // dump()

  void dump(int pos, String indent) {
    if (pos < length) {
      System.out.println(indent + elements.get(pos));
      dump(left(pos), indent + "L ");
      dump(right(pos), indent + "R ");
    }
  } // dump(int, String)

  void swap(int x, int y) {
    Object temp = elements.get(x);
    elements.set(x, elements.get(y));
    elements.set(y, temp);
  } // swap(int, int)

  int parent(int pos) {
    return (pos-1)/2;
  }

  int left(int pos) {
    return 2*pos + 1;
  }

  int right(int pos) {
    return 2*pos + 2;
  }
} // class Heap