2

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.

Gab
  • 7,869
  • 4
  • 37
  • 68
Domin
  • 141
  • 6
  • 5
    @EJP Pointless comment. I think this is the best place to get any chance to "ask the designers". – user11153 Jun 23 '15 at 13:56
  • So is the question how to implement Dijkstra really? See http://stackoverflow.com/questions/6952660/java-priority-queue-reordering-when-editing-elements – drrob Aug 19 '15 at 09:36
  • ... which is in turn a possible duplicate of http://stackoverflow.com/questions/1871253/updating-java-priorityqueue-when-its-elements-change-priority – drrob Aug 19 '15 at 09:36
  • @drrob I am not asking how to implement Dijkstra! That is stated in the question. – Domin Aug 19 '15 at 12:23
  • @EJP A pointless question would be something like why they implemented max PQ, not min PQ or the other way round – Domin Aug 19 '15 at 12:23
  • have a look to http://stackoverflow.com/questions/9255620/why-does-dijkstras-algorithm-use-decrease-key – Gab Aug 19 '15 at 12:54
  • @Domin I got lost reading that big paragraph explaining why this is a good question. Please just state your question clearly, and if it's any good it'll speak for itself. – drrob Aug 19 '15 at 13:09
  • @drrob Many people rush to decisions like "this question is a duplicate" no matter how original your actual question is. I have questions that get closed and reopened before, and I have to argue at great length to reiterate what I have already said. It is no wonder that he tries to defend himself. – Siyuan Ren Aug 19 '15 at 13:35
  • The only place where `ChangePriority` is useful, at least to my knowledge, is in Dijkstra's algorithm. But in that case, you have to reimplement the whole priority queue to maintain indices of every inserted object, such that the original `ChangePriority` is pointless. – Siyuan Ren Aug 19 '15 at 13:39
  • @SiyuanRen I see your point – drrob Aug 19 '15 at 13:42
  • @SiyuanRen Actually, as strange as it may be, for Dijkstra you don't need Change Priority. You can just go on adding graph vertices to PQ with lower priority each time instead of changing the priority of the original. Then each vertex is inserted to PQ not more then E=V^2 times.so you get the same asymptotic running time (perhaps with bigger constant i.e. 3). – Domin Aug 20 '15 at 09:15
  • @SiyuanRen So do I understand your comment correctly: your suggestion is that you would have to have an awkward interface of the PQ to be able to point at the item which priority needs to be changed? – Domin Aug 20 '15 at 09:20
  • @Gab Thanks, that's really interesting. – Domin Aug 20 '15 at 09:30
  • @Domin In Dijkstra you may want to decrease the priority of a certain item. But finding that item in a typical binary heap requires a linear scan, which would bump up the time complexity to O(N^2). So the "priority queue" in Dijkstra's have to include a mapping from every object to its index in the heap, and that is not a trivial change to the priority queue implementation. – Siyuan Ren Aug 20 '15 at 10:02
  • @SiyuanRen That was exactly my initial guess. Thanks. – Domin Aug 20 '15 at 11:19

2 Answers2

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.

Nick
  • 2,524
  • 17
  • 25
0

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

Bhoot
  • 2,614
  • 1
  • 19
  • 36
  • 1
    Why do you think "overall runtime complexity of your code would still remain the same"? The 'remove()' is a linear search, right? i.e. pretty bad? – Tim Cooper May 08 '17 at 06:42