1)  Heap class is almost fully defined.  It is abstract.
It's purpose is to be the base class for BinaryHeap class.
This leaves the design open for polymorphism, even though
it is not used in this project.

2)  Output operator for Heap must be defined.  It must work
for all subclasses, too.  Also, the output must be a 
comma-space-separated list of the elements on the heap - with
no comma-space after the last element. For a BinaryHeap, the 
elements will be in level-order.  The order might be different 
for other types of heaps.  
   What's the best way to do this?  Use an iterator.  Each
heap provides the appropriate iterator (a BinaryHeap provides
a level-order iterator).  This also makes the separator situation
lots easier.
   Students have seen this type of code before.  It won't hurt
for them to see it again:

    template <class T>
    ostream & operator<<(ostream & os, const Heap<T> & hp)
    {
        Iterator<T> * iter = hp.GetIterator(); 
        while (iter->HasNext())
	  {
	     os << iter->Next();
	     if (iter->HasNext())
	        os << ", ";    // or whatever separate is wanted
          }
        return os;
    }

I don't mind if you give students this code.  I really want them
to start thinking this way.

3)  The level-order iterator for BinaryHeap is a piece of cake.
Given that BinaryHeap aggregates an ArrayList, the iterator
is just the iterator provided by ArrayList.  The work was
already done in Project 2.

4) I think you will have to provide some help with the idea of 
generic comparisons.  There are a number of slick ways to handle the
comparisons.

We do NOT want to see code like:

   if (this heap is a min-heap) 
     if (x < y)
       {
          ...
       }
   else if (this heap is a max-heap)
     if (x > y)
       {
          ...
       }

  Ugly! Gag!


  We want code that does not do case analysis and works for
both min and max heaps.  The way I propose in the handout 
is to choose a Compare function upon construction of the heap.

(Another way is to define a Comparator class and dynamically 
bind it to the heap.  I considered requiring this, but then decided 
it might be too hard.  It's actually much nicer, but, sigh, it's
not to be this semester.)

  The method I chose is straight out of the C programming 
bag-o-tricks.

  A Compare function pointer has the type
bool (* Compare)(const T&, const T&); 

Read this  as "Compare is a pointer to a function that
takes two const T references as parameters and returns bool"

It compares two things of type T and returns true if the
comparison is "correct", false otherwise.  Here are two
sample Compare functions for primitives like int, char, float, etc.

// This one returns true if lhs <= rhs (i.e. lhs precedes rhs)
template <class T>
bool Precedes(const T& lhs, const T& rhs);

// This one returns true if lhs >= rhs (i.e. lhs follows rhs)
template <class T>
bool Follows(const T& lhs, const T& rhs);


When a BinaryHeap is constructed, it is constructed as either a
min-heap or a max-heap.  The constructor assigns the appropriate
function to the Compare data member:

After that, any comparisons made are made using the Compare
function.  For example, in SiftDown, you see the lines

          if  (Compare(right_child, left_child))
	    child += 1;  // use right child

Similar lines exist in other methods.

5) The only real difference between a min-heap and a max-heap is in
the SiftUp and SiftDown methods.

6) It may be handy to define the Replace method for List.  Its
signature would be:

  virtual bool Replace(int pos, T& newelem) = 0;

It replaces the element at pos with newelem.  Returns false if
pos is not valid.

It would be implemented in ArrayList (and in LinkedList, but that's
not used in this Project).

It's not required to add Replace to List, it's just allowed. It
can make life lots easier.

7) You should explain the drawing idea.  Some of the students might
not have ever done Snoopy drawings on line printers, so they might
not catch on to how to set up character arrays and send them
to the printer.

8) Remind students to submit IteratorConstants if they use it.
Executable must be named Proj4.  

9) Design and style will count heavily in grading.  Use accessors and
mutators, not direct reference to private data members.  Should
not be much need for friend functions.  Use one or more auxiliary 
files to keep the size of Proj3.C small.