import java.util.*;


/**
      This implementation of a binary heap is primarily from the
   Weiss text.

*/


public class BinaryHeap
{

   /** the number of elements in the heap */
   protected int currentSize;

   /** the array representing the heap */
   protected Comparable[] array;

   /** the default size of the array */
   protected static final int DEFAULT_CAPACITY = 100;


   /** The zero argument constructor builds
       a heap of the default capacity
   */

   public BinaryHeap()           {
     this(DEFAULT_CAPACITY);     }


   /**
   This binary heap construtor builds
      a heap of the given capacity
   @param capacity the desired capacity
   */

   public BinaryHeap(int capacity)     {
     currentSize=0;
     array=new Comparable[capacity+1]; }


   /**
   This constructor is not from Weiss.
   It takes a vector, converts the vector
     to an array, and then calls buildHeap
     to turn the array into a heap
   @param v the vector
   */  

   public BinaryHeap(Vector v)         {
     this(v.size());
     currentSize=v.size();
     for (int i=0; i<v.size(); i++)
       array[i+1]=(Comparable) v.get(i);
     buildHeap();                      }


   /**
   Empty the current queue
   */


   public void makeEmpty()             {
     currentSize=0;                    }


   /**
   This method is not functional -- it
   always returns false.  It is provided
   only for consistency with Weiss
   @return a boolean value indicating
   whether the queue is full
   */

   public boolean isFull()             {
     return false; //??
  }


   /**
   This method deterimines whether the
     queue is empty
   @return a boolean value indicating
   whether the queue is empty
   */

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


   /**
   This method inserts an element
     into a priority queue.  Unlike
     Weiss's corresponding method, it
     does not check whether the queue
     is full, and does not throw an
     exception if it is.
   @param x the element to insert
   */
   // Otherwise the algorithm is that
   //   of Weiss

   public void insert(Comparable x)
   // throws Overflow
                         {
     if (isFull())
       {} // throw new Overflow();
     int hole=++currentSize;
     for (; hole>1 &&
            x.compareTo(array[hole/2])<0;
          hole/=2)
       array[hole]=array[hole/2];
       array[hole]=x;                      }


   /**
   This method finds but does not delete the
   minimum element of the heap.
   @return the minimum element
   in the heap, according to the comparison
   method for the implementation of Comparable
   */

   public Comparable findMin()             {
     return array[1];
      }


   /**
   This method deletes an element from
   the heap.
   @return the deleted element, which will be
   the minimum element in the heap,
   according to the comparison
   method for the implementation of Comparable
   */

   public Comparable deleteMin()           {
     if (isEmpty())
       return null;
     Comparable minItem=findMin();
     array[1]=array[currentSize--];
     percolateDown(1);
     return minItem;                       }


   /**
   Move the element downward in the heap
   that is originally located at a given position
   @param hole the index representing the initial
    position
   */

   protected void percolateDown(int hole)             {
     int child;
     Comparable tmp=array[hole];
     for (; hole*2<=currentSize; hole=child)         {
       child=hole*2;
       if (child!=currentSize &&
           array[child+1].compareTo(array[child])<0)
         child++;
       if (array[child].compareTo(tmp)<0)
         array[hole]=array[child];
       else
         break;                                     }
     array[hole]=tmp;                                 }


  /**
  This method takes a binary tree without the
  heap property, and gives it the heap property.
  The resulting heap contains the same elements
  as the original tree.
  */

  public void buildHeap()                             {
    for (int i=currentSize/2; i>0; i--)
      percolateDown(i);                               }

}