Will the priority queue element change the call to the queue?

Question

I have priority_queue and I want to change part of its contents (priority value), will it resort to the queue?

It depends on whether it uses push / pop (more likely because you just need to “insert” and not resort to the whole) or when accessing a vertex or pop file.

I really want to change some items 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 paste into it. Your assignment at the end will have zero effect on the order of the priority queue, as well as the values ​​stored inside it.

Answer 2

Unfortunately, the std::priority_queue class does not support the increase/decrease_key operations you are looking for. Of course, you can find the element inside the heap that you want to update, and then call make_heap to restore the binary invariants of the heap, but this cannot be done as efficiently as it should with std:: container / algorithms. Scan the heap to search for the O(N) element O(N) , and then make_heap is O(N) on top of this - it should be possible to make increase/decrease_key in O(log(N)) for binary heaps that properly support updates.

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

Answer 3

Well, after a short search, I learned how to "resort" to the queue, so after each change in the priority value, you need to call:

 std::make_heap(const_cast<Type**>(&queue.top()), const_cast<Type**>(&queue.top()) + queue.size(), ComparerClass()); 

And the line should then be

 std::priority_queue<Type*,vector<Type*>,ComparerClass> queue; 

Hope this helps.

Answer 4

I stumbled upon this issue while considering using priority queues for the A * algorithm.

Basically, C ++ priority queues are a very limited toy.

Dynamically changing the priority for a delivered item requires a complete reconstruction of the underlying heap manually, which is not even guaranteed to work with this STL implementation and is extremely inefficient.
In addition, obscene code is required to restore the heap, which must be hidden in yet another confusing class / template.

Like many other things in C ++, you have to reinvent the wheel or find some fashionable library that re-created it for you.