CODEWITHSUNDEEP
c++
MJeremy
MJeremy

Reputation: 1250

How to reduce the value of C++ priority queue?

Consider I have a min priority queue with the smallest value on the top, I hope to reduce the value on the top so that the property of the queue would still be maintained and time complexity would be O(1). How to do that?

I have seen the question here how to change the value of std::priority_queue top()?

Where take the value out, modify it and push it back basically would be O(logN) complexity, I wonder can I make use of the property of reducing the value so that there is no need to push the value back again?

Upvotes: 0

Views: 564

Answers (2)

Hanjoung Lee
Hanjoung Lee

Reputation: 2152

I see the point of this question differently from others. Based on this question,

I have a min priority queue with the smallest value on the top, I hope to reduce the value on the top so that the property of the queue would still be maintained and time complexity would be O(1).

With std::priority_queue, you can't. We may try a hack like const_cast<int &>(pq.top()) = lesser_value_than_top. It could work in some implementations, but it is NOT safe.

So, I would like to suggest building your own PQ with an array-based heap, and you can just change the top's value without log(N) work, as long as it is a value equal or less than the current top.

Upvotes: 0

StPiere
StPiere

Reputation: 4263

The standard priority queue doesn't support changing the keys.

What you are looking for is something similar to another data structure called Indexed Priority Queue, often used by Dijkstra algorithm.

The Indexed Prioirty queue supports 2 more methods in it's API: increaseKey and decreaseKey enabling modifying the key's itself.

The STL doesnt define indexed priority queue. You'd probably need to implement one by yourself or look for some third party implementation.

Upvotes: 1

Related Questions