Gabriel Rebello - 4 months ago 22

C++ Question

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.

`#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;

}

`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`

`heap.push_back(0)`

`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] = 0`

and `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)
```