8

我有一个priority_queue，我想修改它的一些内容（优先级值），那么队列会被使用吗？

这取决于它是使用 push/pop（更有可能，因为您只需要“插入”，而不是全部使用），还是在访问 top 或 pop 时。

我真的很想更改队列中的一些元素。像这样的东西：

priority_queue<int> q;

int a=2,b=3,c=5;
int *ca=&a, *cb=&b, cc=&c;

q.push(a);
q.push(b);
q.push(c); //q is now {2,3,5}

*ca=4;

//what happens to q?
// 1) {3,4,5}
// 2) {4,2,5}
// 3) crash
4

4 回答 4

4

priority_queue复制您推入其中的值。您最后的分配将对优先级队列的顺序以及存储在其中的值产生零影响。

于 2012-12-24T01:45:20.113 回答
4

不幸的是，std::priority_queue该类不支持increase/decrease_key您正在寻找的操作。当然，可以在堆中找到要更新的元素，然后调用make_heap以恢复二进制堆不变量，但这不能像std::容器/算法那样有效。扫描堆以查找项目O(N)，然后make_heap是最重要的 -对于正确支持更新的二进制堆，应该O(N)可以这样做。increase/decrease_keyO(log(N))

Boost 提供了一组优先队列实现，它们可能比std::priority_queue（配对堆、斐波那契堆等）更有效，并且还提供可变性，因此您可以有效地执行动态更新。所以总的来说，使用 boost 容器可能是一个更好的选择。

于 2012-12-24T02:11:34.820 回答
2

在考虑将优先级队列用于 A* 算法时，我偶然发现了这个问题。

基本上，C++ 优先级队列是一个非常有限的玩具。

动态更改排队元素的优先级需要手动执行底层堆的完整重建，这甚至不能保证在给定的 STL 实现上工作并且效率非常低。
此外，重建堆需要丑陋的代码，这些代码必须隐藏在另一个混淆的类/模板中。

至于 C++ 中的许多其他东西，您将不得不重新发明轮子，或者找到任何为您重新发明它的时尚库。

于 2014-09-14T20:52:50.563 回答
2

好的，经过一番搜索，我发现了如何“重新排序”队列，因此在每次更改优先级值后，您需要调用：

std::make_heap(const_cast<Type**>(&queue.top()),
     const_cast<Type**>(&queue.top()) + queue.size(),
     ComparerClass());

然后必须排队

std::priority_queue<Type*,vector<Type*>,ComparerClass> queue;

希望这可以帮助。

于 2012-12-24T02:14:11.510 回答