Why Java's Priority Queue lacks a Change Priority method?

Question

I was wondering why Java's Priority Queue does not support the ChangePriority. I have read somewhere (with no details) that dropping ChangePriority allows one to use more efficient implementation, but have no idea how it could be possible - binary heap seems quite simple/efficient data structure - can't see any space for improvement. Another clue could be that it might take awkward interface to indicate to the PQ which element (presumably a position in the heap) changes its priority, but still I am novice to Java to come up with a conclusion.

Edit: Why this could be not a pointless question? If you are new to Java (especially from C/C++ background) you start wondering about things like where did all the pointers go, or how do I implement Dijkstra in Java etc.

The first question has been answered many times the second one doesn't have, as far as I understand it, a simple answer. One could expect that in such a language like Java you have all the usual programming tools ready at hand, working out of the box, encapsulated in a nice class wrapper. But suddenly you have to implement by yourself a PQ with decrease key method, which perhaps is an more awkward thing to do in Java then in C/C++. In this question I'm not asking how to implement Dijkstra (this has been nicely answered in some other thread). There still could be many applications of PQ which can't be sorted out without a decrease key/prio method, eg. if there are far more priority updates then items in PQ. In Dijkstra there are at most V

So one might expect that there is some serious reasons why Java's PQ lacks change priority. The reasons are probably interesting in their own regardless of actual Java's PQ interface.

Answer 1

While I cannot be sure about why the change priority methods have not been exposed for PriorityQueue, it can be observed that when the priority of the object in the PriorityQueue changes, you can simply remove and reinsert the object.

This behavior of PriorityQueue exists because whenever a new object is inserted in the the queue, it is put at the appropriate position (based on object's comparator). This works well because every time something is pulled out of the queue, no re-computations are required to find the element with min/max priority. This brings in the limitation that object's priority cannot be changed once it has been inserted in the queue.

It is true that removing and re-inserting the object is slower, it can be seen that overall runtime complexity of your code would still remain the same. That said, if you are interested in looking at custom java implementations of Priority Queue, this can be a good place to start - http://algs4.cs.princeton.edu/24pq/IndexMinPQ.java.html

Answer 2

I suspect that design choice is because its a Queue. The basic operations of a queue are enqueue and dequeue. A Priority Queue is different in that as part of the enqueue operation it allows an element be prioritized over others. Most Queue implementations don't allow for manipulating the elements once it is put in, although some provide a peek capabilities. So our data type being a queue, I'm not really "supposed" to mess with the internal arrangement, nor should I care per se. If I'm using a queue, I basically want First In First Out behavior. Queue

That being said, how could you achieve the behavior you want? I would recommend a TreeMap. It gives you queue-like functionality, I can grab the first or last element via firstKey() or lastKey(), while still providing artificial ordering via my own Comparator interface as well as access to the entries via a Key, albeit your Key implementation would have to provide both a unique identifier as well as it's sort order.