Instructions
Create at least two files:heap.h and test.cpp. If you want to create a heap.cpp file as well, that is fine.
You can complete this assignment in one of two ways.
Object Oriented
Create aHeap class with the methods
public: Heap(int *data, size_t size);public: void queue(int i);public: int dequeue();
The constructor must heapify the data argument (which should point at the first element of an array of integers, and the array's size should be given by size_t).
The queue method must enqueue the argument in such a way that when dequeue is called, the elements will be dequeued in order; from the greatest integer to the lowest. The queue and dequeue methods must both be O(log(n)).
Procedural
Create the functions:void heapify(int *data, size_t size);void queue(int* data, size_t size, int i);int dequeue(int* data, size_t size);
The heapify function should heapify the input in place.
The queue and dequeue functions then accept a pointer to the heapified array as their first argument, and the size of the array as their second argument.
The main function should go in
test.cpp and it should be similar to the main function in Homework 1, that is it should call a bunch of tests.
I won't spell out what the tests should be the way I did in Homework 1, but at a minimum you must test queue and dequeue for a variety of inputs.
HINT: You can make additional functions and methods. A function or method named
heapUp seems like it might be useful.