0

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;
}
};
JKB
  • 123
  • 2
  • 9

0 Answers0