So our assignment was to generate 30 random integers (from 10-200) and insert them into our heap class and display the heap. Then we are to remove the max one by one into an array to display in sorted order, however everytime I try i end up with problems such as the following:
Randomly Generated heap:
187 176 170 166 162 163 87 93 145 158 116 150 118 39 58 35 42 38 83 46 15 109 69
88 149 77 91 22 26 25
Sorted heap:
22, 25, 26, 35, 38, 39, 42, 46, 58, 69, 77, 83, 118, 87, 88, 91, 93, 109, 116, 1
45, 149, 150, 158, 162, 163, 166, 170, 176, 2293224, 187,
It ends up being mostly sorted, and the next to last number always seems to be pulled from out of bounds of the heap, and I have no idea what I'm doing wrong.
Heap.h:
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
175
176
177
178
179
180
181
182
183
|
#include <iostream>
using namespace std;
const int MAX_SIZE = 100; //the maximum amount of elements our heap should have. This may be changed to any number so long as memory permits, depending on how the heap will be used.
template <class ItemType>
class Heap
{
public:
Heap();
int left(int) const;
int right(int) const;
int parent(int) const;
void insert(const ItemType&);
ItemType remove_max();
bool IsEmpty() const;
bool IsFull() const;
int count() const;
ItemType value(int) const;
void display() const;
private:
ItemType array[MAX_SIZE];
int size; //how many elements are in the heap
void ReHeap(int);
};
//default constructor - initialize private variables
template <class ItemType>
Heap<ItemType>::Heap()
{
size = 0;
}
/* The left(), right(), and parent() functions return the index positions of a node's children and parent.
Since the index position of each element correspond to their logical position in the heap, the functions use
simple formulae that are derived by observing the heap structure. */
template <class ItemType>
int Heap<ItemType>::left(int root) const
{
if (root >= 0 && (2*root+1) <= size)
return (2*root+1);
else
return -1;
}
template <class ItemType>
int Heap<ItemType>::right(int root) const
{
if (root >=0 && (2*root+2) <= size)
return (2*root+2);
else
return -1;
}
template <class ItemType>
int Heap<ItemType>::parent(int child) const
{
if (child > 0 and child <=size)
return (child-1)/2;
else
return -1;
}
/* The insert() function accepts the new item value as its parameter. It works by inserting the new item at
the end of the heap, and swapping positions with the parent, if the parent has a smaller value than the
item. The new item continues to travel up the heap, swapping its position with its new parents until the
item's parent is larger than it. */
template <class ItemType>
void Heap<ItemType>::insert(const ItemType &item)
{
array[size] = item;
int loc = size;
size++; //increase size
while(loc != 0 && array[loc] > array[parent(loc)])
{
ItemType temp = array[loc]; //swap items
array[loc] = array[parent(loc)];
array[parent(loc)] = temp;
loc = parent(loc); //move to next position
}
}
/* The remove_max() removes the item with the highest priority and returns its value. The item is swapped
with the last item, and elements is updated to one less.
The item should not be physically deleted, it will remain as part of the array. It will not be part of the
heap since size will be updated, and the heap goes only as far as (size - 1).
The new root may not have the largest priority, therefore the ReHeap() function should be used to insert the
new root into its proper position, thus conserving the heap property. */
template <class ItemType>
ItemType Heap<ItemType>::remove_max()
{
if(size < 0)
return false; //heap is empty
int max = array[0];
array[0] = array[size]; //move max off of heap
size--;
ReHeap(0);
return max;
}
/*The ReHeap() function checks of either of root's children are bigger than it, in which case the bigger
child is swapped with root. The process is then continued using recursion, on root's new children. The
function stops when root is bigger than both of its children.
*/
template <class ItemType>
void Heap<ItemType>::ReHeap(int root)
{
int done=0, max, temp;
while (root*2 <= size)
{
if (root*2 == size)
max = root * 2;
else if (array[root * 2] > array[root * 2 + 1])
max = root * 2;
else
max = root * 2 + 1;
if (array[root] < array[max])
{
swap(array[root],array[max]);
root = max;
}
else
return;
}
}
//The rest of our member functions are easy to implement.
template <class ItemType>
void Heap<ItemType>::display() const
{
if(!IsEmpty())
{
cout << endl;
for (int i=0; i < size; i++)
cout << array[i] << " ";
cout << endl;
}
}
template <class ItemType>
int Heap<ItemType>::count() const
{
return size;
}
template <class ItemType>
ItemType Heap<ItemType>::value(int pos) const
{
assert(pos < size); //is pos a valid index in the heap
return array[pos];
}
template <class ItemType>
bool Heap<ItemType>::IsEmpty() const
{
return (size == 0);
}
template <class ItemType>
bool Heap<ItemType>::IsFull() const
{
return (size == MAX_SIZE);
}
|
driver.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
|
#include <cstdlib>
#include <ctime>
#include <iostream>
#include "Heap.h"
using namespace std;
int main()
{
int myArray[30];
int i;
srand((unsigned)time(0));
int random;
Heap<int> myHeap;
for(i=1; i<31; i++) //fill heap with 30 random integers between 10-200
{
random = rand() %190 +10;
myHeap.insert(random);
//cout << random << " ";
}
cout << "\nRandomly Generated heap:\n";
myHeap.display();
cout << "\nSorted heap:\n";
for(i=29; i >=0; i--)
{
myArray[i] = myHeap.remove_max();
}
for(i=0; i<30; i++)
cout << myArray[i] << ", ";
}
|
