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 the ordering of array$-$based heaps, review Chapter $17\mathrm{.}2$ in Walls and Mirrors, pp$.519-528.$

Use this file as the starting framework for your template:$$ myHeap.hDownload myHeap.h

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

After completing the heap algorithms in the template, 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$).$

Other Notes

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.

Do not rewrite the starter template.$$ Add your code within the existing template using the provided definitions and variables within the myHeap class.

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.