c++ - C++ 中是否有一个堆类支持更改除头部之外的元素的优先级？

Question

我有一个事件优先级队列，但有时事件优先级会发生变化，所以我想将事件请求者的迭代器维护到堆中。如果优先级发生变化，我希望在 log(n) 时间内调整堆。我将始终只有一个迭代器指向堆中的每个元素。

score 10 · Accepted Answer

10

看看 Boost 的可变堆。

于 2009-05-29T19:30:44.917 回答

score 3 · Accepted Answer

我很高兴地报告 Boost 现在添加了一个带有一些出色数据结构的 Boost.Heap 库。

这样做的好处是斐波那契堆支持在恒定摊销时间内更改优先级。

不幸的是，所有可变堆都是基于节点的（换句话说，它们具有@wilx 所建议的额外间接性）。@Feruccio 对 Boost 的“可变堆”的回答有代码，如果您愿意在值类型中包含指向句柄的指针，则可以编写基于向量的可变堆。

score 2 · Accepted Answer

这听起来像你需要更多的间接性。而是将指向事件的指针存储在优先级队列中。当队列中某些元素的优先级发生变化时，将其删除并重新插入。

score 0 · Accepted Answer

这里的一个警告是你最终会得到不稳定的事件排序，即具有相同优先级的事件的排序是未定义的（阅读“它们将被重新排序”。）

4 回答 4