I have implemented a heap class which takes, as a constructor argument, a boolean value which specifies if the object should be a min heap or a max heap. The getTop() method should return and remove the max value from the max heap.
If I initialize the heap as such:
Heap maxHeap(true); // This will be a max heap.
int values[]{1, 5, 3, 2, 10, 7};
for (const int &value : values) {
maxHeap.insert(value);
}
I get two different outputs depending on how I write cout:
cout << maxHeap.getTop() << endl
<< maxHeap.getTop() << endl
<< maxHeap.getTop() << endl;
// Output: 5
// 7
// 10
Compared to the following block, which also happens to have the desired output:
cout << maxHeap.getTop() << endl;
cout << maxHeap.getTop() << endl;
cout << maxHeap.getTop() << endl;
// Output: 10
// 7
// 5
Replacing maxheap.getTop() with integer literals will result in the correct behavior and there will not be a difference between both ways. Reading similar Stack Overflow posts, I learned that the C++ standard does not specify order for operators with the same level of precedence. Is it just a coincidence that the first code block will work correctly with integer literals? What could possibly cause this behavior? Any insight on this would be greatly appreciated.
Edit: Below is the code of my Heap class.
class Heap {
public:
vector<int> v;
bool isMax;
Heap(bool isMax) : isMax(isMax) {
// Don't use first element.
v.push_back(-1);
}
Heap &insert(int value) {
v.push_back(value);
swim(v.size() - 1);
return *this;
}
int getTop() {
int topValue = v[1];
v[1] = v.back();
v.pop_back();
sink(1);
return topValue;
}
int size() {
return v.size() - 1;
}
private:
void swim(int index) {
while (!isOrdered(index)){
swap(index / 2, index);
index /= 2;
}
}
void sink(int index) {
int childIndex = findReplacementIndex(index);
while (childIndex > 0) {
if (!isOrdered(childIndex)) {
swap(childIndex / 2, childIndex);
index = childIndex;
}
else {
break;
}
childIndex = findReplacementIndex(index);
}
}
int findReplacementIndex(int parentIndex) {
if (2 * parentIndex >= v.size()) {
return -1;
}
else if (2 * parentIndex + 1 >= v.size()) {
return 2 * parentIndex;
}
else if (isMax) {
return v[2 * parentIndex] > v[2 * parentIndex + 1] ?
2 * parentIndex : 2 * parentIndex + 1;
}
else {
return v[2 * parentIndex] < v[2 * parentIndex + 1] ?
2 * parentIndex : 2 * parentIndex + 1;
}
}
void swap(int index1, int index2) {
int tmp = v[index1];
v[index1] = v[index2];
v[index2] = tmp;
}
bool isOrdered(int childIndex) {
if (childIndex < 2 || childIndex >= v.size()) {
return true;
}
int parent = v[childIndex / 2];
int child = v[childIndex];
return isMax ? parent > child : parent < child;
}
};