make_heap 更改向量中的值后未按预期工作？

Question

我正在尝试使用 make_heap 实现 Dijkstra 的堆算法，它（希望）按递减顺序对向量进行排序以创建优先级队列，但由于某种原因，排序全错了如果我更改了一个值但我不知道为什么。

代码：

#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

有趣的是，如果我在推送其他元素之前将 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

会是什么？提前致谢。

Answer 1

C++ 标准未指定标准库应如何实现堆。所以你不应该期待一个特定的安排。 C++ 标准仅指定行为。

TL；DR；

heap[0] = 0和heap.push_back(0)有区别。前者不会改变容器的大小，而后者会。 odd/even 大小容器的堆表示可能不同；没关系，当我们使用适当的函数访问它时，我们想要的只是堆行为。

同样，每当你使用像std::make_heap这样的函数时，你应该使用它的关联函数（std::push_heap和std::pop_heap）来访问容器（这保证了堆属性的维护容器）。

对其进行任何其他修改都可能导致容器失去其堆属性。这包括：

heap[0] = 0;

甚至：

heap.push_back(0)

Answer 2

要成为一个有效的堆，heap[i] <= heap[(i - 1) / 2] for all i > 0.

在这两种情况下，make_heap() 都在创建一个有效的堆。第一个有 5 个元素，第二个有 6 个。我不明白你问题的部分内容，但它们似乎与 make_heap().

无关

make_heap 更改向量中的值后未按预期工作？

make_heap not working as expected after changing value in vector?

c++

sorting

algorithm

heap

c++11

代码：

输出：

输出：