This lab is a practice in constructing a basic binary heap and performing heap sort. Implement insert, copy constructor, getHeight, getSize, contains, removeFirst, operator[], and sort. Note: please follow the lecture as some of this will be done in class.
#ifndef HEAP_H
#define HEAP_H
#include <string>
template<class T> class Heap { private:
/* Lets fill out in class. */ public:
/* Creates an empty heap. */ Heap();
/* Does a deep copy of the array into the heap. */ Heap(const T *array, const int size);
/* Add a given value to the heap.
* Must maintain ordering!
*/ void insert(const T &val);
/* Returns the height of the heap. */ int getHeight();
/* Returns the size of the heap. */ int getSize();
/* Returns the index if an item if exists in the heap.
* Otherwise return -1.
*/ int contains(const T &val) const;
/* Retrieves the element at position pos */ T& operator[](const int pos);
/* Removes and returns the first element */
T& removeFirst();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/* Performs a Heap Sort and returns an array of the sorted * elements.
* Note: the heap is empy after the sort!
*/
T* heapSort();
~Heap();
};
/* Since heap templated, we include the .cpp.
* Templated classes are not implemented until utilized (or explicitly
* declared.)
*/
#include "heap.cpp"
#endif
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
Write some test cases:
Create some test cases, using cxxtestgen, that you believe would cover all aspects of your code.
Memory Management:
Now that are using new, we must ensure that there is a corresponding delete to free the memory. Ensure there are no memory leaks in your code! Please run Valgrind on your tests to ensure no memory leaks!
