Write a C++ program that will implement and test a linked heap, and will use a namespace for all the reasons talked about in class.

A heap, sometimes called a priority heap, or a priority queue, partially arranges the elements in it. The elements in it that can be compared. For the sake of simplicity, we'll assume that we always want the least element in this heap.

At a minimum, a heap supports the following operations:

• top (returns the top of the heap)
• pop (removes what is on the top of the heap)
• insert (puts something into the heap)
• empty (returns a boolean if it is empty or not)

The top of the heap will always be the least element.

In future assignments we may ask you to support more operations on this heap.

You may assume that the heap is not empty for all of the above methods, except for empty(), in which you need to actually figure out and return if it is empty or not.

You will have your implementation of a heap be a templated class, complete with a constructor, destructor, an overloaded assignment operator, a copy constructor, and a dump method that outputs everything.

Similar to the binary search tree being used to implement a set in the videos linked from from Module 1, and also similar to the deque in Assignment 2, you will want to

• have a node struct (you may want to rename it to something else, like heap_node or similar) that has the appropriate left and right links in it, which you will update and access as you do what you do
• have your templated class (a reasonable name for it would be heap that has a pointer to the top node. Note that this might be NULL if the heap is empty.

You will want to have your main function test out all of those operations, including constructor, destructor, copy constructor, assignment operator, dump method and all the ones listed earlier that are specific to heaps. It should output what it is doing along the way, to help with debugging and to help show that your code works.

Your program should read from input until there is a sentinel value (your choice, but I recommend zero for simplicity sake), and as it reads in, put it into the heap. Then it should test various other things involving that heap. Somewhere, as part of this test, it should, in a loop, output the top, pop off the top, and repeat, until it is empty.

This must be a linked implementation using pointers. Implementations that use arrays will be left ungraded.

Test your program in parts. I recommend first the constructor, then inserting things into the heap, and then various combinations of calling the various other methods, and so on, checking empty all along the way, until at the end you pop everything off and empty is true.

Be sure to follow the requirements in the Documentation Requirements handout including a good README file.

REMEMBER this is for the assignment on namespaces, so be sure that you're using a namespace.