Iterate and modify c++ priority queue

Question

I want a priority queue where I can iterate and modify. In other words, non-constant iterator.

It seems that the std::priority_queue<T> does not support changing values of keys to protect corruption of the structure.

I found boost::heap::prioity_queue to support mutability of keys of priority_queue / modification of values with update functions to maintain invariant of data structure.

boost also supports iterators, yet they are const iterators and do not allow change.

Answer 1

The standard has functions to help maintain a heap, make_heap, push_heap and pop_heap. Combine those with std::vector or another random access container, and it is not much work to maintain a heap which you can iterate over.

Example:

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

Also note that all the heap functions have an optional parameter for a comparator so that you can control the ordering of your heap.