Does changing a priority queue element result in resorting the queue?

Question

I have a priority_queue, and I want to modify some of it's contents (the priority value), will the queue be resorted then?

It depends if it resorts on push/pop (more probable, becouse you just need to "insert", not resort whole), or when accessing top or pop.

I really want to change some elements in the queue. Something like that:

priority_queue<int> q;

int a=2,b=3,c=5;
int *ca=&a, *cb=&b, cc=&c;

q.push(a);
q.push(b);
q.push(c); //q is now {2,3,5}

*ca=4;

//what happens to q?
// 1) {3,4,5}
// 2) {4,2,5}
// 3) crash

Answer 1

priority_queue copies the values you push into it. Your assignment at the end there will have zero effect on the order of the priority queue, nor the values stored inside of it.

Answer 2

Unfortunately, the std::priority_queue class doesn't support the increase/decrease_key operations that you're looking for. Of course it's possible to find the element within the heap you want to update, and then call make_heap to restore the binary heap invariants, but this can't be done as efficiently as it should be with the std:: container/algorithms. Scanning the heap to find the item is O(N) and then make_heap is O(N) on top of that - it should be possible to do increase/decrease_key in O(log(N)) for binary heaps that properly support updates.

Boost provides a set of priority queue implementations, which are potentially more efficient than the std::priority_queue (pairing heaps, Fibonacci heaps, etc) and also offer mutability, so you can efficiently perform dynamic updates. So all round, using the boost containers is potentially a much better option.