Exercise 5
----------
Implement a Heap data structure, as described in section
6.3, pages 219 to 234.

The "Template" for this exercise is in Heap.java.
Copy all of the files Heap.java, HeapException.java,
Test.java, and Ex5.class (when available). 

To implement the exercise edit and submit Heap.java

NOTE: The Heap will be defined only over Strings. 
NOTE: To compare strings you MUST use the method 
        private int compareTo(String s1, String s2)
      This will keep track of the number of comparisons performed
      by your implementation.

The Heap data structure has an array S of Strings, an integer 
capacity, and last (the position of the last entry) 

The array S runs from S[0] right up to S[cap+1], so that
 - the 1st element of the heap is in S[1]
 - the last element of the heap is in S[last]

Note that the heap property is that given an element S[i] 
 - the element to the left of S[i] is greater 
   than or equal to S[i], 
 - the element to the right of S[i] is
   greater than or equal to S[i]

Note that the elements of S can be viewed as
a binary tree, numbered in the conventional way
 - the element to the left of S[i] is S[i*2]
 - the element to the right of S[i] is S[i*2 + 1]

Implement the following methods  
 (1) public int size(){}
 (2) public boolean isEmpty(){}
 (3) public String minElement(){}
     This delivers the smallest element/string in the heap
 (4) public void insertElement(String e){}
     Insert an element/string into the heap
     maintaining the heap property, and
     throwing an exception if the heap is full
 (5) public String removeMinElement(){}
     Throw an exception if the heap is empty
     otherwise, remove the smallest element/string 
     in the heap, maintaing the heap property. Return
     as a result the element/string removed.


To Submit, do as usual, 
  - copy Heap.java to ~/cs233lab/Heap.java
  - cs233check

Deadline
Friday the 25th February 2000, at 5 o'clock


Hints, Hints and more Hints
1. You need to do "up heap bubbling" and "down
   heap bubbling", so maybe implement private 
   methods for these
2. You will be, in some sense, implementing a binary tree 
   within the array S. So, what is Left and what is Right? 
   Maybe implement private methods to get the element to the 
   Left/Right of i.
3. Belts and braces? To debug/develop, how about a method
   isHeap, that checks that the heap property is present.
   You might run this after an insertion or deletion to make
   sure everything is okay. You might also corrupt S so
   that you can confirm that isHeap() actually detects 
   absence of the heap property.