增加优先级队列中的优先级

Question

我想降低优先级队列中元素的优先级吗？我如何在对数时间内实现这一点？

我知道优先级队列是作为最大堆实现的。但是，如果我修改队列中的任何元素，然后在队列上调用make_heap，则元素数需要线性时间。

参考资料：排队/

Answer 1

用对数复杂度执行更新的唯一方法是自己实现优先级队列，这样您就可以使用著名算法。

std::priority_queue的实现不是由标准指定的(例如，它很可能是D类堆)，因此在不重新构建队列的情况下，您无法移植地更新优先级。出于同样的原因，您不能使用std::make_heap和相关函数。

Answer 2

您不能使用std::priority_queue来完成它。但是，如果您可以访问堆的内部结构，则是可能的。如果有指向元素的指针，则可以降低元素的优先级，然后对此元素使用siftDown过程仅用于修复堆。