HeapPQ
. This is a "min-heap" in
which at every vertex the children are no smaller than the parent. A
"max-heap" would be one in which at every vertex, the children are no
larger than the parent.
The only implementation difference between a min-heap and a max-heap
is the direction of the comparisons made between elements. Why not
design a binary heap data structure that can be made a min-heap or a
max-heap at construction time? Why not, indeed! You'll do that in
this project. Of course, if the heap can be either a min-heap or a
max-heap, it no longer makes sense to have operations such as
FindMin
and DeleteMin
; these will become
just Find
and Delete
.
We also recognize that there is an opportunity for future extension of
the heap to allow leftist heaps, binomial heaps, and other kinds of
heaps as well as binary heaps. We therefore design our classes to
allow polymorphism and dynamic binding at some future time (not in
this project). Our binary heap class is to be called
BinaryHeap
and it is to be derived from the abstract
class Heap
. Definitions of
Heap
and
BinaryHeap
are given below.
The Heap
definition is complete, but you must complete the
BinaryHeap
definition.
One more thing. We want to be able to draw a picture of the heap. We don't need a fancy picture, just something that lets us see the tree structure. You will develop a simple drawing function in this project.
You are free to use your own designs for any classes in this project.
The only restriction is that you must use the Heap
class
as the base class for BinaryHeap
. You must also use the
main
function given below. Of course, you may name your files anything you
wish with the two restrictions that the executable must be named
Proj4
and there must be a makefile named either
makefile
or Makefile
. Lots of freedom here,
so design carefully.
HeapPQ
class in the text and develop your classes
Heap
and BinaryHeap
. Write a function that
draws a picture of a given BinaryHeap
of
char
. Some hints on how to write a DrawHeap
function are given below.
Heap
class. There's not much to
do, just finish some documentation, guard the header file, implement
the IsEmpty() and ~Heap()
methods, and write
the non-member function
template <class T>
ostream & operator<<(ostream & os, const Heap<T> & heap);
- Write the
BinaryHeap
class as a sub-class of
Heap
. Although some of the definition has been provided,
you must complete it and implement the methods.
- Write the
DrawHeap
function. You should define this
function in an "auxiliary" file such as Proj4Aux.C
.
- Write the function
void HandleCommandLine(int argc, char *argv[], char heap_type[], char ** arr);
for use with the main
function. This function prints a
usage message to cerr
and exits if the command line is
incorrect. If the command line is OK, the heap_type
and
arr
parameters have the appropriate values upon return.
For the meaning of the parameters, study the call in the main
function. In order to keep the Proj4.C
file small, you
should define HandleCommandLine
in your auxiliary file.
- Test your code with a number of inputs.
- Remember, the name of your executable must be
Proj4
.
Also, make sure your code meets the usual style guidelines in the
Project Organization handout.
Heap
/* 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; };
BinaryHeap
BinaryHeap
. You are free
to modify it in any reasonable way. It must be derived from
Heap
and must be a concrete class.
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(); };
main
Functionint 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; } } }
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.
8,4,9,2,5,1,6,3,7
. This is the sequence you get if you
read the tree from left-to-right, ignoring the levels.
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.