Write a heap template using the array-based format. You can make it either a minheap or maxheap — your choice. If you need a quick refresher on how array-based heaps work, review Chapter 17.2 in Walls and Mirrors, pp. 519 – 528.

A template file myHeap.h is included in this module to help you get started. You are not required to use this template but it can supply a framework for your thinking.

Requirements
1) The heap must implement the following public interface:

bool isEmpty(); // returns TRUE if the heap has no items
int getNumberOfNodes(); // returns the number of items in the heap
ItemType peekTop(); // if a minheap, returns the lowest element, else the highest
bool add(ItemType &newData); // adds ‘newData’ to the heap
bool remove(); // removes the lowest/highest element of the heap
void clear(); // deletes all items in the heap
The private methods in the class are up to you, but some are provided in the example code.

For the functions that return ‘bool’, they should return true if the operation succeeded, false otherwise. For example add() should return false if the heap is at max capacity before the add. The remove() method would return false if called on an empty tree, true otherwise.

2) It must define two constructors:

One that accepts an array and a size, which will cause the template to “heapify” (heapCreate(), which would call heapRebuild() repeatedly in the supplied code) array and uses it as the initializing heap. The input array can be in any order.
A default constructor which accepts no parameters and initializes the heap to zero elements and a default max capacity (this is supplied for you).
Testing the Code
Write a test driver for your new heap that tests each of the constructors as follows:

1) Constructor with a supplied array case: generate a random array of 10 integers. Create a new heap from the array (passing it as an argument to the constructor), and output the results of 10 peekTop() and remove() operations. This should output the array in sorted order.

2) Constructor for an empty heap case: starting with an empty heap (using the constructor that accepts no arguments), add 10 random integers. Output the results of 10 peekTop() and remove() operations. This should also output the array in sorted order.

3) Test the isEmpty() and getNumberOfNodes() functions by outputting their value at some point (your choice).

Please do not “hard code” any values. It is not sufficient to simply output sorted numbers, i.e. code that does not implement an array-based heap that can accept any set of numbers will not receive credit.

What to Submit
To complete this lab, submit these files:

1) Your completed myHeap.h. If there are special instructions for building and running the code, please include those in the comments with your submission.

2) Your test driver .cpp file with a main() function that runs the above tests.

Alternatively, if you prefer to implement your heap and main() in a single .cpp file, submit that one file with everything.

Example Output
The output should be similar to the following — this is for a maxheap.

Existing array test
——————-
Random array:
40 92 99 4 10 44 39 93 98 95
Number of nodes (isEmpty() is FALSE):
10
10 removes:
99 98 95 93 92 44 40 39 10 4

Starting with empty array test
——————————
Random array:
83 2 11 19 21 44 58 20 91 33
Number of nodes (isEmpty() is TRUE):
0
10 removes:
91 83 58 44 33 21 20 19 11 2