c++ - 迭代修改c++优先级队列

Question

我想要一个可以迭代和修改的优先级队列。换句话说，非常量迭代器。

看来 std::priority_queue<T>不支持更改键的值以保护结构的损坏。

我找到了 boost::heap::prioity_queue支持priority_queue键的可变性/使用更新函数修改值以保持数据结构的不变性。

boost 也支持迭代器，但它们是 const 迭代器，不允许更改。

Answer 1

该标准具有帮助维护堆的功能，make_heap , push_heap和 pop_heap .将它们与 std::vector 或其他随机访问容器相结合，维护一个可以迭代的堆并不需要太多工作。

例子:

std::vector<int> heap = {1,3,5,7,9};
std::make_heap(heap.begin(), heap.end());

// add an element
heap.push_back(4);
std::push_heap(heap.begin(), heap.end());

// remove an element
std::pop_heap(heap.begin(), heap.end());
heap.pop_back();

// multiply each element by 2
for (auto & i : heap)
    i *= 2;

Demo

另请注意，所有堆函数都有一个用于比较器的可选参数，以便您可以控制堆的顺序。