import structure5.*;

/**
 * A binary heap implemented as an implicit binary tree on
 * top of the structure5.Vector class.
 */
class VectorHeap<E extends Comparable<E>> {
  protected Vector<E> data;

  /**
   * Returns a new VectorHeap.
   */
  public VectorHeap() {
    data = new Vector<E>();
  }

  /**
   * Compute the location of the child to the left of i.
   * 
   * @param i The index of a subtree root.
   * @return A location.
   */
  protected static int left(int i) {
    return 2 * i + 1;
  }

  /**
   * Compute the location of the child to the right of i.
   * 
   * @param i The index of a subtree root.
   * @return A location.
   */
  protected static int right(int i) {
    return 2 * i + 2;
  }

  /**
   * Computer the location of the parent of i.
   * 
   * @param i The index of a subtree root.
   * @return A location.
   */
  protected static int parent(int i) {
    return (i - 1) / 2;
  }
  
  /**
   * Returns the max element.
   *
   * @return An element.
   */
  public E findMax() {
    if (data.size() == 0) return null;
    return data.get(0);
  }

  /**
   * Extract the max element, heapify, then return the max.
   * 
   * @return The max element.
   */
  public E extract() {
    if (data.size() == 0) return null;
    E max = data.get(0);
    data.set(0, data.get(data.size() - 1));
    data.remove();
    heapDown(0);
    return max;
  }

  /**
   * Insert an element, then heapify.
   * 
   * @param value The value to insert.
   */
  public void insert(E value) {
    data.add(value);
    heapUp(data.size() - 1);
  }

  /**
   * Returns true iff there are no elements in the tree.
   * 
   * @return True if empty.
   */
  public boolean isEmpty() {
    return data.size() == 0;

  }

  /**
   * Compare the given leaf with its parent and swap up recursively
   * until no more swaps remain. Ensures that the max heap
   * property is maintained.
   * 
   * @param leaf The index of a leaf.
   */
  public void heapUp(int leaf) {
    if (leaf > 0) {
      int parentIdx = parent(leaf);
      E value = data.get(leaf);
      if (value.compareTo(data.get(parentIdx)) > 0) {
        data.set(leaf, data.get(parentIdx));
        data.set(parentIdx, value);
        heapUp(parentIdx);
      }
    }
  }

  /**
   * Compare the given root with its children and swap down recursively
   * until no more swaps remain. Ensures that the max heap
   * property is maintained.
   * 
   * @param root
   */
  public void heapDown(int root) {
    int leftIdx = left(root);
    // if there is no left child, there are
    // no children, so do nothing
    if (leftIdx < data.size() - 1) {
      E value = data.get(root);

      // there is a left child
      E leftVal = data.get(leftIdx);

      int rightIdx = right(root);
      if (rightIdx < data.size()) {
        // there is also a right child
        E rightVal = data.get(rightIdx);

        // since there are two children, we need to find
        // the larger of the children and compare
        // against that one
        if (rightVal.compareTo(leftVal) > 0) {
          // right is the bigger of the children
          // is right larger than the root? if so, swap
          if (rightVal.compareTo(value) > 0) {
            data.set(rightIdx, value);
            data.set(root, rightVal);
            heapDown(rightIdx);
            return;
          }
        }
      }
      // there is only a left child
      // is root smaller than left?
      if (leftVal.compareTo(value) < 0) {
        data.set(leftIdx, value);
        data.set(root, leftVal);
        heapDown(leftIdx);
      }
    }
  }

  /**
   * A simple visualization of our heap.
   */
  public String toString() {
    return "<VectorHeap: " + data + ">";
  }

  /**
   * Some test code.
   * 
   * @param args Ignored.
   */
  public static void main(String[] args) {
    VectorHeap<Integer> v = new VectorHeap<>();

    v.insert(56);
    v.insert(5);
    v.insert(57);
    v.insert(0);
    v.insert(-7);
    v.insert(99);

    // what does our heap look like?
    System.out.println(v);

    // let's remove some elements
    System.out.println("Removing: " + v.extract());
    System.out.println("Removing: " + v.extract());

    // now what does it look like?
    System.out.println(v);
    
    // what's the max now?
    System.out.println(v.findMax());
  }
}