我有一个事件优先级队列,但有时事件优先级会发生变化,所以我想将事件请求者的迭代器维护到堆中。如果优先级发生变化,我希望在 log(n) 时间内调整堆。我将始终只有一个迭代器指向堆中的每个元素。
问问题
3590 次
4 回答
10
看看 Boost 的可变堆。
于 2009-05-29T19:30:44.917 回答
3
我很高兴地报告 Boost 现在添加了一个带有一些出色数据结构的Boost.Heap 库。
这样做的好处是斐波那契堆支持在恒定摊销时间内更改优先级。
不幸的是,所有可变堆都是基于节点的(换句话说,它们具有@wilx 所建议的额外间接性)。@Feruccio 对 Boost 的“可变堆”的回答有代码,如果您愿意在值类型中包含指向句柄的指针,则可以编写基于向量的可变堆。
于 2012-03-01T20:41:08.173 回答
2
这听起来像你需要更多的间接性。而是将指向事件的指针存储在优先级队列中。当队列中某些元素的优先级发生变化时,将其删除并重新插入。
于 2009-05-29T19:17:26.613 回答
0
这里的一个警告是你最终会得到不稳定的事件排序,即具有相同优先级的事件的排序是未定义的(阅读“它们将被重新排序”。)
于 2009-05-29T19:39:07.270 回答