Description
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!
