How to get the minimum element from a priority queue after modifying the contents of queue

Question

I was trying to implement Dijkstra's algorithm using a priority queue in Java.. Unfortunately it was returning wrong results...I have tracked down the problem. Here's the Problem..After inserting the node weights into the queue,I am modifying those node weight,but when i try to remove the element from the priority queue ,its returning the historical minimum (minimum at the time of insertion).remove() doesn't know that the priority queue has been modified..Any help would be greatly appreciated ...Thanks!

Note:i can add the source code if required

Answer 1

This SO question should help you. The drawback with the PriorityQueue in Java is that the if an inserted element value changes, the priority queue is not re-constructed to reflect the new order. Thus you would have to remove and re-insert the changing elements to satisfy your use case.

Answer 2

The standard interfaces do not provide an update capability. You have use a custom type that implements this. This is because, as stated in the S.O post titled, "Updating Java PriorityQueue when its elements change priority":

You have to remove and re-insert, as the queue works by putting new elements in the appropriate position when they are inserted.

How this affects you is discussed in the S.O post, "Java Priority Queue reordering when editing elements":

A priority queue does not resort all elements whenever an element is added or removed....Doing that would be too expensive. PriorityQueue does not offer an api to inform it about a changed node, as that would require it to provide efficient node lookup, which its underlying algorithm does not support.

The above posts provide alternate methods for your implementation of Dijsktra's algorithm.

Please let me know if you have any questions!

Answer 3

Just like the keys of a Map, the elements you put in a PriorityQueue need to be immutable. The element which is inserted in PriorityQueue is compared against all the existing elements in the PriorityQueue. So, if the underlying element changes, your PriorityQueue will most likely fail to hold the invariants.

An alternative datastructure which you could use could be a TreeSet. The remove operation of TreeSet is O(lg N).