Gabriel Rebello Gabriel Rebello - 21 days ago 5
C++ Question

make_heap not working as expected after changing value in vector?

I'm trying to implement Dijkstra's algorithm with heaps using make_heap, which (hopefully) sorts a vector in decreasing value order in order to make a priority queue, but for some reason the sorting gets all wrong if I change a value and I have no idea why.

Code:



#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
vector<float> heap;

for(int i=0;i<5;i++) heap.push_back(1e9);

heap[0] = 0; // <=== this is a problem for make_heap

for(int i=0;i<heap.size();i++) cout << heap[i] << ' ';
cout << endl;

make_heap(heap.begin(),heap.end());

for(int i=0;i<heap.size();i++) cout << heap[i] << ' ';
cout << endl;

return 0;
}


Output:



Success time: 0 memory: 3468 signal:0
0 1e+09 1e+09 1e+09 1e+09
1e+09 1e+09 0 1e+09 1e+09





A funny thing is that if I change
heap[0] = 0
to a
heap.push_back(0)
before pushing the other elements the sorting works perfectly.

Output:



Success time: 0 memory: 3468 signal:0
0 1e+09 1e+09 1e+09 1e+09 1e+09
1e+09 1e+09 1e+09 1e+09 1e+09 0


What could it be? Thanks in advance.

Answer

It is Unspecified by the C++ standard how a standard library should implement a Heap. So you should not expect a specific arrangement. The C++ standard only specifies the behavior.

TL;DR;

There is a difference between heap[0] = 0and heap.push_back(0). The former doesn't change the size of the container while the latter does. And the heap representatioin for odd/even sized container may be different; it doesn't matter, all we want is a heap behavior when we access it using appropriate functions.


Again, whenever you use functions like std::make_heap, you should use its associated functions (std::push_heap and std::pop_heap) to access the container (this is guaranteed to maintain the heap properties of the container).

Any other modification to it may result in the container losing its heap properties. This includes:

heap[0] = 0;

And even:

heap.push_back(0)
Comments