我正在尝试使用 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
它会是什么?提前致谢。
最佳答案
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)
关于c++ - 更改 vector 中的值后,make_heap 无法按预期工作?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40579647/