Should PriorityQueue allow duplicates?

Note: This issue was originally filed in Base Julia by John Myles White at https://github.com/JuliaLang/julia/issues/4372. In addition to the issue text I've also reproduced the existing comments on the issue.

@johnmyleswhite:

My understanding of priority queues is that they should allow duplicate keys: this is, for example, how the STL and Java priority queue implementations work as far as I can tell (cf. http://stackoverflow.com/questions/251438/stl-priority-queue-with-duplicate-keys-is-it-possible, http://stackoverflow.com/questions/10469701/how-to-configure-java-priority-queue-to-ignore-duplicates). Right now, our implementation doesn't do this because it acts more like a Dict than a queue.

Could we possibly rename our current implementation to PriorityQueueDict and then implement a more standard PriorityQueue that behaves like a queue/array?

@stevengj:

Note that you can use heappush! etcetera if you don't want it to act like a Dict.

@dcjones:

The intention with making it behave like a Dict was to make things like Dijkstra or A* that require updating element priorities easier to write, which is an idea from clojure's priority-map. That struck me as a more common problem than needing to have multiple copies of the same element in the queue. Searching stack overflow for questions about updating priorities in C++ or Java, you get a bunch of answers suggesting you write your own priority queue.

So I'd like to keep the current priority queue in some form. Two priority queue types is one way to address this, we could also change the semantics of the current implementation so that duplicates are allowed q[x] = 100, changes the priority of just one occurrence of x (i.e. most recently enqueued).

@lindahua:

Two different things are involved here: (1) the priority weight/value, which should allow duplicates, and (2) the handle that refers to a particular node in the heap (I think that's what @dcjones mentioned as the key).

The DataStructures.jl package takes a different approach, implementing both a non-mutable heap and a mutable heap. The mutable heap returns a handle when you push an element, with which the user can update the value later (e.g. in Dijkstra's algorithm).

The issue discusses the PriorityQueue implementation, heappush!, and mutable versus non-mutable heaps, but names no source files or tests. First inspect the current PriorityQueue API and its duplicate-key behavior; this issue is not complete until the project chooses and documents a specific queue and handle model.