/*  
   Abstract heap.  May be a min-heap or a max-heap as determined
   by derived concrete classes.
*/
template <class T>
class Heap
{
protected:
  // Constants for determining if min-heap or max-heap
  static const int MIN = 1;
  static const int MAX = 2;

  virtual ~Heap();

  // Sifts up the element at index i in this heap
  virtual void SiftUp(int index) = 0;

  // Sifts down the element at index i in this heap
  virtual void SiftDown(int index) = 0;
public:

  // Adds element x to this heap.
  // Return: true if insertion succeeds, false otherwise.
  virtual bool Insert(const T& x) = 0;

  // Returns the element with top priority in this heap.
  // It is an error to attempt this operation on an empty heap.
  virtual T& Find() = 0;

  // Deletes the element with top priority in this heap.
  // Return: true if deletion succeeds, false otherwise.  Deletion
  // from an empty heap returns false.
  virtual bool Delete() = 0;

  // Accessor for the size of this heap.
  // Return: the number of elements on this heap.
  virtual int GetSize() const = 0;

  // Test for this heap being empty.
  // Return: true if this heap is empty, false otherwise.
  bool IsEmpty() const;

  // Makes this heap be empty
  virtual void MakeEmpty() = 0;

  // A string describing the heap.  For example, the string
  // describing a BinaryHeap in which the top element has highest
  // priority would be "BinaryMaxHeap."  A BinaryHeap in which 
  // the top element has lowest priority would be "BinaryMinHeap."
  // Return: a string description
  virtual char * ToString() = 0;

  // Accessor for an iterator over this heap.  The iterator outputs
  // the heap elements in an order suitable for the type of heap.
  // Return: ptr to the Iterator.
  // Note: dynamically allocated.  User is responsible for
  // storage deallocation.
  virtual Iterator<T> * GetIterator() = 0;
};

Note the use of a function pointer data member Compare. Remember that the only real difference between a min-heap and a max-heap is the direction of the comparisons. Set the Compare function pointer appropriately at construction time, and use it to do comparisons. Your code will be neat and clean and will work for both min heaps and max heaps. You will be graded on how nicely you implement your class. No messy spaghetti code, please. Of course, if you have a different, equally slick way of doing this, feel free to use it. Just be sure your approach is clean and elegant.

/*
 A binary heap.  Constructor(s) determine if it is a min-heap or 
a max-heap. The heap is implicit (stored in  an array rather than 
as an explicit tree.
*/
template <class T>
class BinaryHeap : public Heap<T>
{
private:
  ArrayList<T> _elements;
  int _heaptype;  // either Heap::MIN and Heap::MAX
  bool (* Compare)(const T&, const T&);  // comparison function
               .
               .
               .
protected:
  // Converts _elements into a binary heap.
  void Heapify();

  // Sifts up the element at index i in this heap
  virtual void SiftUp(int index);

  // Sifts down the element at index i in this heap
  virtual void SiftDown(int index);
public:
  // Constructor for min-heap.
  // Optional param: type should be "Min" or "Max".  If missing, or
  // if something other than "Min" or "Max", defaults to "Min"
  BinaryHeap(const char * type = "Min");

  // Construct binary heap using data from initvals.  Length of
  // initvals array is init_len.
  // The actual length of initvals must be initlen - run time 
  // errors may result if it's not.
  // Param: type should be "Min" or "Max".  If something else, heap
  // defaults to min-heap
  // Param: initvals is an array of initial values of length initlen
  // Param: initlen ist the length of initvals
  BinaryHeap(const char * type, T * initvals, int initlen);

  // Copy constructor.
  BinaryHeap(BinaryHeap<T> & bh);

  // Destructor.
  virtual ~BinaryHeap();

               .
               .
               .

  // Accessor for an iterator over this heap.  Outputs the
  // heap elements in level order.
  // Return: ptr to the Iterator.
  // Note: dynamically allocated.  User is responsible for
  // storage deallocation.
  virtual Iterator<T> * GetIterator();
};

int main(int argc, char *argv[])
{
  char heap_type[3];  // "Min" or "Max"
  char * arr;  // string of initial chars from command-line

  HandleCommandLine(argc, argv, heap_type, &arr);

  BinaryHeap<char> heap(heap_type, arr, strlen(arr));

  cout << "Heap is a " << heap.ToString() << endl;
  cout << "Heap = " << heap << endl;
  cout << "Heap Size is " << heap.GetSize() << endl;
  cout << endl;

  cout << "-----------------------" << endl;
  cout << "Heap = " << endl;
  DrawHeap(cout, heap);
  cout << "Top Value = " << heap.Find() << endl;

  int len = heap.GetSize();
  for (int i = 0; i < len; i++)
    {
      cout << "-----------------------" << endl;
      heap.Delete();
      cout << "After Delete operation, Heap = ";
      if (heap.IsEmpty() == false)
	{
	  cout << endl;
	  DrawHeap(cout, heap);
	  cout << "Top Value = " << heap.Find() << endl;
	}
      else
	{
	  cout << "empty" << endl;
	}
    }
}

1. either Min or Max. This is used to determine whether the heap will be a min-heap or a max-heap.
2. a string of characters that will be used to initialize the heap.

umbc9: Proj4 Min FRKBWHNDV

Heap is a BinaryMinHeap
Heap = B,D,H,F,W,K,N,R,V
Heap Size is 9

-----------------------
Heap = 
      B   
    D   H 
  F  W K N
 R V      
Top Value = B
-----------------------
After Delete operation, Heap = 
     D   
   F   H 
  R W K N
 V       
Top Value = D
-----------------------
After Delete operation, Heap = 
    F   
  R   H 
 V W K N
Top Value = F
-----------------------
After Delete operation, Heap = 
    H  
  R   K
 V W N 
Top Value = H
-----------------------
After Delete operation, Heap = 
    K 
  R  N
 V W  
Top Value = K
-----------------------
After Delete operation, Heap = 
   N 
  R W
 V   
Top Value = N
-----------------------
After Delete operation, Heap = 
  R 
 V W
Top Value = R
-----------------------
After Delete operation, Heap = 
  V
 W 
Top Value = V
-----------------------
After Delete operation, Heap = 
 W
Top Value = W
-----------------------
After Delete operation, Heap = empty

To draw the tree, we need to know where to place the elements vertically and horizontally; we need to know the x and y coordinates of each element. We think of the origin of the coordinate system at the upper left. This figure shows a complete binary tree with the vertices numbered in level order.

For a complete binary tree, the y-coordinates are the levels of the elements, equal to the floor of the base-2 log of the element number. For example, element 1 has (x,y)-coordinates (6,0). It occurs 6th in the inorder sequence and lg(1) is zero. As another example, element 6 is at (7,2) because it occurs 7th in the inorder sequence and the floor of lg(6) is 2.

Therefore, given just the number of elements in any complete binary tree, you can generate the x,y positions for each element.

In this project, you are writing a very simple drawing function. It is just an old-fashioned text-based function that does not require a graphics device. Each line (i.e., level) is composed as a string and printed, starting from level 0.