CODEWITHSUNDEEP
javaqueuepriority-queue
user2233125
user2233125

Reputation:

Changing the priority of an element in a PriorityQueue

I know that PriorityQueue automatically sorts the elements when add()ing one by using the objects' compareTo() method. Let's say I want to change the priority of an element in the queue at some point. How do I explicitly order the PriorityQueue to sort itself again, given that the priority of an element has changed?

Upvotes: 5

Views: 4238

Answers (2)

S. Pauk
S. Pauk

Reputation: 5318

The only option is to remove, modify and add back your object. PriorityQueue doesn't update it's internal structure on read. Here's an implimentation of peek() for example:

public E peek() {
    if (size == 0)
        return null;
    return (E) queue[0];
}

As you could see doesn't check if elements order has been changed.

Upvotes: 1

L. Blanc
L. Blanc

Reputation: 2310

Remove the object, change its priority, and re-add it to the queue.

My intuition is that the data structure doesn't normally watch the internal state of the objects and that it requires an add() or remove() operation to trigger a re-invocation of the comparator. A call to Collections.sort(), would also work, but you would have to transform the queue to a list and then back to a queue. This might make more sense if you change a lot of priorities at one time.

Better still, you might update n priorities, then add and remove the last one.

Upvotes: 4

Related Questions