c++ - 可更新的优先级队列

Question

C++ 标准库中是否内置了任何允许我在优先级队列/堆之类的数据结构中工作的东西(即，始终可以从列表中弹出最高值，可以定义如何为自定义类确定最高值等)但允许我更新堆中的键？我正在处理相当简单的数据，确切地说是成对数据，但我需要能够轻松地更新堆中给定键的值，以便我的算法运行。在 C++ 中实现此目的的最佳方法是什么？

Answer 1

二叉堆(C++ 标准库中优先级队列的实现方式)不支持任意更新键操作。如果更新不频繁，一种常见的方法是在外部将原始项目标记为无效，并使用新键重新插入该值；当弹出一个无效值时，它会被忽略。

替代方案是使用支持更新 key 的不同 PQ 实现，例如二项式堆。二项式堆具有通过摆动指针而不是移动值来操纵的特殊优势。这简化了实现更新 key 和删除等操作的任务。