2

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

function
  • 1,298
  • 1
  • 14
  • 41

3 Answers3

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.

Community
  • 1
  • 1
Prahalad Deshpande
  • 4,709
  • 1
  • 20
  • 22
  • Thanks for the help!!! – function Jun 14 '15 at 05:42
  • This isn't a drawback of Java's implementation; any efficient priority queue implementation assumes the elements in the queue are not re-weighted in flight. This is also true of most other common collections (Java or otherwise) like hashmaps and trees. – dimo414 Jun 14 '15 at 05:54
  • @dimo414 Agreed!! :) – Prahalad Deshpande Jun 14 '15 at 05:54
  • @dimo414 if you will see the c++ priority_queue, you will find it rearranges on updating a value so it is a drawback of PriorityQueue of Java. – mss May 14 '21 at 00:41
  • Updating the the collection itself does trigger a reordering. But *mutating* an element in the collection does not. That is almost certainly true of C++'s implementation, unless the queue is significantly more complex than it should be. – dimo414 May 15 '21 at 05:25
1

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!

Community
  • 1
  • 1
Devarsh Desai
  • 5,984
  • 3
  • 19
  • 21
0

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).

bsd
  • 2,707
  • 1
  • 17
  • 24