package jutil;


/**
 * A binary heap is a complete binary tree except possibly for the bottom level.
 * The element of every node is greater than the element of its parent. Thus,
 * the smallest element is stored at the root of the tree.
 */
public class BinaryHeap implements PriorityQueue {
   /**
    * The children of elems[i] are stored in elems[2i] and
    * elems[2i + 1], the root (= min) is in elems[1].
    */
   private Comparable[] elems;
   /**
    * The number of elements stored.
    */
   private int size;
   /**
    * The capacity of the heap is a power of 2.
    */
   private int capacity;
   /**
    * Initializes capacity to 2^exp.
    */
   public BinaryHeap(int exp) {
	   capacity = (int)Math.pow(2, exp);
	   elems = new Comparable[capacity];
	   size = 0;
   }
  /**
   * Sets elems[i] to null for each i.
   */
  public void clear() {
	  for(int i = 0; i < capacity; i++) {
		  elems[i] = null;
	  }
	  size = 0;
  }
  /**
   * Returns the size of the heap.
   * @return The number of non-null elements.
   */
  public int size() { return size; }
  /**
   * Returns true if size is 0.
   * @return true if size = 0.
   */
  public boolean isEmpty() { return size() == 0; }
   /**
    * Initializes capacity to 2^8 = 512.
    */
   public BinaryHeap() { this(8); }
   /**
    * Converts heap into a LISP-style string
    * representation of a heap. Use toArray if
    * this is too confusing.
    */
   public String toString() {
	   return toString(1);
   }
   /**
    * Recursively converts the heap rooted at element i into
    * a LISP style string representation of a tree.
    */
   private String toString(int i) {
	   if (size < i) return "";
	   if (size < 2 * i) return " " + elems[i]; // no kids
	   String result = "(" + elems[i] + " ";
	   result += toString(2 * i);
	   result += toString(2 * i + 1);
	   result += ")";
	   return result;
   }

   /**
    * Converts heap into a sorted array.
    * Caution: array order may not reflect.
    * Caution: this method is inefficient.
    * heap order in the case of equal items.
    * @return the heap as a sorted array.
    */
   public Comparable[] toArray() {
	   Comparable[] temp = new Comparable[size];
	   System.arraycopy(elems, 1, temp, 0, size);
	   java.util.Arrays.sort(temp);
	   return temp;
   }
   /**
    * Inserts element according to its natural order.
    * The algorithm inserts x at the bottom of the tree,
    * then repeatedly swaps x with its parent until
    * a smaller parent is encountered.
    *
    * @param x   element to be inserted.
    * @throws OverflowException if the heap is full.
    */
   public void insert(Comparable x) throws OverflowException {
      // percolate "hole" up until x fits
      if (capacity <= size) throw new OverflowException();
      int hole = ++size;
      for(; hole > 1 && x.compareTo(elems[hole/2]) < 0; hole /= 2)
         elems[hole] = elems[hole/2];
      elems[hole] = x;
   }
   /**
    * Removes and returns the smallest element. After elems[1] is
    * removed, the largest element moves to the root and then
    * percolates down to its new position.
    *
    * @return null if the tree is empty, elems[1] otherwise.
    */
   public Comparable deleteMin() {
      if( isEmpty()) return null;
      Comparable minItem = elems[1];
      elems[ 1 ] = elems[size--];
      percolateDown( 1 );
      return minItem;
   }
   /**
    * A helper method that repeatedly swaps a node with its
    * smaller child until there are no smaller children.
    * @param hole  position of the element to percolate down.
    */
   private void percolateDown( int hole ) {
      int child;
      Comparable tmp = elems[ hole ];
      for( ; hole * 2 <= size; hole = child ) {
         child = hole * 2;
         if( child != size &&
            elems[ child + 1 ].compareTo( elems[ child ] ) < 0 )
               child++;
         if( elems[ child ].compareTo( tmp ) <= 0 )
            elems[ hole ] = elems[ child ];
      else
         break;
      }
         elems[ hole ] = tmp;
  }
}