import java.util.ArrayList;

/**     MinHeap implementation of a priority queue
 *
 * MinHeap returns the smallest available entry on remove.  This
 * implementation takes advantage of java.util.ArrayList in
 * Java 5.0.
 *
 * Implemented with method "enter" to make an entry into a valid
 * MinHeap, maintaining the data structure as a valid MinHeap.
 *
 * There is also the method "append" which appends to the end of
 * the ArrayList, thereby (most probably) invalidating the
 * MinHeap.  In that case, once the appends have completed, the
 * user need to invoke "heapify()" to make the data structure a
 * valid MinHeap.
 *
 * Author:  Timothy Rolfe, based on LOTS of previous people.
 */
public class MinHeap implements PriorityQueue
{
   // No constructor required.  Initialize as an empty ArrayList
   ArrayList<Comparable> heap = new ArrayList<Comparable>();
   int size = 0;             // Initial size, of course, is zero.
   boolean valid = true;     // Initial empty queue is valid.

   //  Removes all of the elements from this priority queue
   public void clear()  {  heap.clear();  }

   // Is the MinHeap empty?  Check the ArrayList.
   public boolean isEmpty()  {  return heap.isEmpty();  }

   // Is the MinHeap valid?  Return the flag.
   public boolean isValid()  {  return valid;  }

   // Enter item into a valid MinHeap, retaining the heap property.
   public void enter ( Comparable item )
   {  if ( !valid )  correct();
      size++; heap.add(item);
      upHeap();
   }

   // Add to the end of the ArrayList WITHOUT heap corrections.
   public void append ( Comparable item )
   {  size++; heap.add(item);  valid = false; }

   // Once all the appends are finished, make it a valid heap again.
   public void correct ()
   {  valid = true;

      for ( int k = size/2; k >= 0; k-- )
         downHeap (k);
   }

   // Show the next item for priority queue removal
   public Comparable peek ( )
   {  return heap.get(0);  }

   // Remove an item from the heap, moving an entry from the back,
   // and then restore the heap property.
   public Comparable remove ( )
   {  Comparable   rtn = null,
                   item;       // Value to be moved

      if ( size > 0 )
      {  rtn  = heap.get(0);        // At the front is the smallest
         item = heap.remove(--size);// Note predecrement.
         if ( size > 0 )
         {  heap.set ( 0, item );   // Plop it into the front
            downHeap ( 0 );
         }
      }
      return rtn;
   } // end remove

   // Restore the heap property, based on the fact that only the
   // heap[size-1] entry is potentially out of place.
   private void upHeap()
   {  int child  = size - 1;
      int parent = (child-1) / 2;   // Note:  rooted at [0]
      Comparable item   =  heap.get(child);   // Item to position

      // Haven't gone over the top AND the parent is out of place.
      while ( child > 0 && item.compareTo(heap.get(parent)) < 0 )
      {  // Copy down from the parent (out of place).
         heap.set(child, heap.get(parent));
         // Reset who is the child and who is the parent.
         child = parent;
         parent = (child-1) / 2;
      }
      // Move the value into where it belongs.
      heap.set(child, item);
   } // end upHeap

   // Restore the heap property, based on the fact that the heap is
   // valid BELOW the entry at heap[parent].
   private void downHeap ( int parent )
   {  int child = parent*2 + 1;
      Comparable   item = heap.get(parent);

      while ( child < size )
      {  // Select the SMALLER child (MinHeap implementation)
         if ( child+1 < size &&
            heap.get(child).compareTo(heap.get(child+1)) > 0 )
            child++;
         // Exit condition before you run out of heap:
         if ( item.compareTo(heap.get(child)) <= 0 )
            break;
         heap.set(parent, heap.get(child));
         parent = child;
         child = parent+parent + 1;
      }
      heap.set(parent, item);
   } // end downHeap
} // end class MinHeap