Write a heap template using the array-based format. You can make it function either a minheap or maxheap -- your choice. If you need a quick refresher on how array-based heaps work, review Chapter 17.2 in the book, 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.

myHeap.h:

#ifndef MY_HEAP_ #define MY_HEAP_

template class myHeap { private: // Start with a small default size static const int DEFAULT_CAPACITY = 24; ItemType *items;

int itemCount; // Current count of heap items int maxItems; // Maximum capacity of the heap

// Returns the array index of the left child (if exists). int getLeftChildIndex(const int nodeIndex) const; // Returns the array index of the right child (if exists). int getRightChildIndex(int nodeIndex) const; // Returns the array index of the parent node. int getParentIndex(int nodeIndex) const; // Tests whether this node is a leaf. bool isLeaf(int nodeIndex) const; // Converts a semiheap to a heap. void heapRebuild(int nodeIndex); // Creates a heap from an unordered array. void heapCreate(); public: myHeap(); myHeap(const ItemType someArray[], const int arraySize); ~myHeap(); // HeapInterface Public Methods: bool isEmpty() const; int getNumberOfNodes() const; ItemType peekTop() const; bool add(const ItemType& newData); bool remove(); void clear(); };

template int myHeap::getLeftChildIndex(const int nodeIndex) const { return (2 * nodeIndex) + 1; }

template int myHeap::getParentIndex(const int nodeIndex) const { return (nodeIndex - 1) / 2; }

template int myHeap::getRightChildIndex(const int nodeIndex) const { return (2 * nodeIndex) + 2; }

template void myHeap::heapRebuild(const int subTreeNodeIndex) { }

template void myHeap::heapCreate() { for (int index = itemCount / 2; index >= 0; index--) { heapRebuild(index); } }

// Constructor that accepts an existing array template myHeap:: myHeap(const ItemType someArray[], const int arraySize): itemCount(arraySize), maxItems(2 * arraySize) { }

// Default constructor template myHeap::myHeap(): itemCount(0), maxItems(DEFAULT_CAPACITY) { items = new ItemType[DEFAULT_CAPACITY]; }

// Default destructor template myHeap::~myHeap() { delete items; }

// Return whether the heap is empty template bool myHeap::isEmpty() const { return itemCount == 0; }

// Return the total number of nodes template int myHeap::getNumberOfNodes() const { return itemCount; }

// Remove the root of the heap and rebuild it template bool myHeap::remove() { }

// Clear all items (note we do not resize the array here). template void myHeap::clear() { itemCount = 0; }

// Return the value at the root of the heap template ItemType myHeap::peekTop() const { return items[0]; }

// Add a new item to the heap template bool myHeap::add(const ItemType& newData) { } #endif /* !MY_HEAP_ */

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 &newItem); // adds 'newitem' 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() will 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.

Testing the Code

Write a test driver for your new heap that tests each of the constructors as follows:

1) Generate a random array of 10 integers (you might be able to reuse your code from the previous lab for filling an array of random integers). Create a new heap from the array, and output the results of 10 peekTop() and remove() operations -- this will output the array in sorted order.

2) Starting with an empty heap, add 10 random integers. Output the results of 10 peekTop() and remove() operations, again this will output the array in sorted order.

3) Also 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 the correct answer, i.e. code that does not implement an array-based heap that can accept any set of items will not receive credit.

What to Submit

Submit two files as follows.

1) Your completed myHeap.h (you can use any file or class name, as long as it implements the heap as above). If there are special instructions for building and running the code, please include those in the comments.

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.

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