c++ - 增加优先级队列中的优先级

Question

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

我知道优先级队列是作为最大堆实现的。但是，如果我修改队列中的任何元素，然后对其调用 make_heap，它将花费元素数量的线性时间。

引用:http://www.cplusplus.com/reference/queue/priority_queue/

Answer 1

执行对数复杂度更新的唯一方法是自己实现优先级队列，所以你可以使用well-known algorithms .

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