问题 C ++中是否有一个堆类支持更改除head之外的元素的优先级？

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

10045

2018-05-29 19:08

起源

看看Boost的可变的堆。

2018-05-29 19:30

谢谢，如果我最终不得不自己动手，我将使用该片段开始。 - Neil G

结束了这个解决方案 - Neil G

@Ferruccio谢谢，救了我好45分钟和几个虫子。 - Ramadheer Singh

@NeilG你试过简单地使用std :: map吗？键入优先级，值是具有相同优先级的事件的向量。事件只需要在桶中存储它的位置。这就是我现在使用的内容，我很好奇这里建议的解决方案是否（更快）... - AlwaysLearning

@AlwaysLearning降低a的优先级 map 是O（log（n））。如果使用Fibonacci堆，它将是O（1）摊销时间。 - Neil G

看看Boost的可变的堆。

2018-05-29 19:30

谢谢，如果我最终不得不自己动手，我将使用该片段开始。 - Neil G

结束了这个解决方案 - Neil G

@Ferruccio谢谢，救了我好45分钟和几个虫子。 - Ramadheer Singh

@AlwaysLearning降低a的优先级 map 是O（log（n））。如果使用Fibonacci堆，它将是O（1）摊销时间。 - Neil G

我很高兴地报告说Boost现在增加了一个 Boost.Heap库和一些恒星数据结构。

这样做的好处是Fibonacci堆支持在不变的摊销时间内改变优先级。

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

2018-03-01 20:41

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

2018-05-29 19:17

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

2018-05-29 19:39

您可以在log（n）时间从堆中删除任意元素。 - Neil G

是的，你是对的，正在考虑别的东西:) - Nikolai Fetissov

没问题：） - Neil G