c++ - 更改 vector 中的值后，make_heap 无法按预期工作？

Question

我正在尝试使用 make_heap 通过堆实现 Dijkstra 算法，它(希望)按递减顺序对 vector 进行排序，以便创建优先级队列，但出于某种原因，如果我更改值并且我不知道为什么，排序就会出错。

代码:

#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++ 标准仅规定了行为。

长话短说；

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

---

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

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

heap[0] = 0;

甚至:

heap.push_back(0)