JuliaCollections
PriorityQueue tie breaking
For some applications it would be helpful to be able to specify some sort of tie breaking scheme for a PriorityQueue. As far as I am aware, there is no such feature at the moment? E.g. for some applications I would like to retrieve the newest key if there are two keys with equal priority.
May I work on this issue? Thanks! I am thinking that if we use lexicographical ordering for breaking ties in case of strings. Should we 'time stamp' for checking newest key? Only issue with the 'time stamp' is that it will cost memory.
Do we currently allow ties at all? I think we do not.
I think we should allow ties, but make not promise as to how they will be broken, just that they will. In general implementation wise, always breaking in favor of newest or oldest makes sense
As i was going through the code, Priority queue is implemented as array of key value pairs in which values are defined as priorities.Priority queue does not allow same keys (ref. https://github.com/JuliaCollections/DataStructures.jl/blob/master/src/priorityqueue.jl#L46) but nothing as such is mentioned for values(priority). Therefore ties can occur.
In current implementation of priority queue the feature to retrieve the newest key if there are two keys with equal priority is already there. Is lexicographical ordering in case of Strings for settling ties desirable?
Is lexicographical ordering in case of Strings for settling ties desirable?
No, i don't think it is. I thinkl ties should be broken arbitarily, most likely determined in implmentation via most/least recent
If that is the case, this issue should be closed. Ties are allowed and there is a deterministic way in which they are broken. Also, by now I am convinced that a priority queue should not be expected to do more than determining the priority of an element based of a real priority value.
Wikipedia:
In some implementations, if two elements have the same priority, they are served according to the order in which they were enqueued, while in other implementations, ordering of elements with the same priority is undefined.
For any ordering preference that can not be expressed by a real number, a priority queue might be the wrong data structure in the first place.
thinking about it some more, and back to my undergrad data structures classes; It is my belief that a priority queue with all elements having same priority should degrade to being a plain old queue.
Thus all ties should be broken in favor of the first one queue'd.
per the wikipedia quote:
In some implementations, if two elements have the same priority, they are served according to the order in which they were enqueued
I am in favor of ties being broken in favor of the first one queued. This is currently not the case (item -1 skips ahead of item 0, even though all items have priority 0 and -1 arrived after 0):
julia> q=PriorityQueue()
PriorityQueue{Any, Any, Base.Order.ForwardOrdering}()
julia> enqueue!(q, 1, 0)
PriorityQueue{Any, Any, Base.Order.ForwardOrdering} with 1 entry:
1 => 0
julia> enqueue!(q, 0, 0)
PriorityQueue{Any, Any, Base.Order.ForwardOrdering} with 2 entries:
1 => 0
0 => 0
julia> enqueue!(q, -1, 0)
PriorityQueue{Any, Any, Base.Order.ForwardOrdering} with 3 entries:
1 => 0
-1 => 0
0 => 0
