CODEWITHSUNDEEP
c++c++11priority-queue
ibp73
ibp73

Reputation: 650

Increase priority in priority queue

I want to decrease the priority of an element in a priority queue? How do I achieve that in logarithmic time?

I know priority queues are implemented as max heaps. But if I modify any element in the queue and then call make_heap on it, it will take linear time in the number of elements.

Reference: http://www.cplusplus.com/reference/queue/priority_queue/

Upvotes: 2

Views: 820

Answers (2)

Anton Savin
Anton Savin

Reputation: 41301

The only way to perform updating with logarithmic complexity is to implement the priority queue yourself, so you can use well-known algorithms.

The implementation of std::priority_queue is not specified by the standard (for example it can well be d-ary heap), so you can't portably update the priority without rebuilding the queue. For the same reason you can't use std::make_heap and related functions.

Upvotes: 3

kraskevich
kraskevich

Reputation: 18546

You cannot do it using std::priority_queue. However, it is possible if you have an access to the internal structure of the heap. If you have a pointer to the element, you can decrease the priority of an element and then use siftDown procedure for this element only to fix the heap.

Upvotes: 1

Related Questions