-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathmain.cpp
174 lines (143 loc) · 4.46 KB
/
main.cpp
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
#include <iostream>
#include <algorithm>
#include <exception>
#include <stdexcept>
#include <iomanip>
using namespace std;
/* ***************************************************
Class Definition
****************************************************** */
class MinHeap
{
private:
int* data; //array containing the heap
int capacity; //maximum size
int heapSize; //current logical size
///--------------Heap helper functions--------------
int getLeftChildIndex(int index); //get index of left child
int getRightChildIndex(int index); //get index of right child
int getParentIndex(int index); //get index of parent
public:
void clear();
int getTop();
int removeTop();
void add(int value);
MinHeap(); //capacity of 100
MinHeap(int maxItems);
virtual ~MinHeap();
MinHeap(const MinHeap& other);
MinHeap& operator=(const MinHeap& other);
friend std::ostream& operator<<(std::ostream& os, const MinHeap& theHeap);
};
/* ***************************************************
Class Implementation
Complete the add function.
Complete the removeTop function.
****************************************************** */
MinHeap::MinHeap()
{
heapSize = 0;
capacity = 100;
data = new int[100];
}
MinHeap::MinHeap(int maxSize)
{
heapSize = 0;
capacity = maxSize;
data = new int[maxSize];
}
MinHeap::~MinHeap()
{
delete [] data;
}
MinHeap::MinHeap(const MinHeap& other)
{
heapSize = other.heapSize;
capacity = other.capacity;
data = new int[100];
std::copy(other.data, other.data+heapSize, data);
}
MinHeap& MinHeap::operator=(const MinHeap& rhs)
{
if (this == &rhs) return *this; // handle self assignment
heapSize = rhs.heapSize;
capacity = rhs.capacity;
data = new int[100];
std::copy(rhs.data, rhs.data+heapSize, data);
return *this;
}
ostream& operator<<(ostream& os, const MinHeap& theHeap) {
os << left;
for(int i = 0; i < theHeap.heapSize - 1; ++i) {
os << "[" << i << "]:" << setw(4) << theHeap.data[i];
}
os << "[" << theHeap.heapSize - 1 << "]:" << setw(3) << theHeap.data[theHeap.heapSize - 1];
return os;
}
int MinHeap::getLeftChildIndex(int index) {
return index * 2 + 1;
}
int MinHeap::getRightChildIndex(int index) {
return index * 2 + 2;
}
int MinHeap::getParentIndex(int index) {
if(index == 0)
throw logic_error("Can't get parent of 0");
return (index-1) / 2;
}
void MinHeap::clear() {
heapSize = 0;
}
int MinHeap::getTop() {
if(heapSize == 0)
throw logic_error("getTop in empty heap");
return data[0];
}
int MinHeap::removeTop() {
if(heapSize == 0)
throw logic_error("removeTop in empty heap");
//swap first and last elements
std::swap(data[0], data[heapSize-1]);
heapSize--; //logically remove the old first element
//merge the new root element back down into heap
int curIndex = 0;
//drift down - know we can stop once we reach a leaf (last half of the array)
while(curIndex < heapSize / 2) {
int leftIndex = getLeftChildIndex(curIndex);
int rightIndex = getRightChildIndex(curIndex);
///TODO - Find index of smaller child
/// Make sure to check if right child exists (index is less than heap size)
/// If no right child, left child is smaller be default
///TODO - if current value greater than or equal to smallest child, break
/// otherwise, swap the two and update curIndex to new location
}
//return the old first element
return data[heapSize];
}
void MinHeap::add(int value) {
if(heapSize == capacity)
throw logic_error("add in full heap");
//add new value to next spot in heap
data[heapSize] = value;
int curIndex = heapSize; //location of item just added
///TODO - swap our way up until current location is root
heapSize++; //increment size
}
/* ***************************************************
Class Implementation
****************************************************** */
int main()
{
MinHeap m;
cout << "---------------Building Heap---------------" << endl;
for(int i = 50; i > 0; i-=5) {
m.add(i);
cout << m << endl;
}
// cout << "---------------Removing top five items---------------" << endl;
// for(int i = 0; i < 5; i++) {
// cout << "Removed " << m.removeTop() << endl;
// cout << m << endl;
// }
return 0;
}