-
Notifications
You must be signed in to change notification settings - Fork 242
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
PriorityQueue tie breaking #498
Comments
May I work on this issue? |
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. |
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. |
No, i don't think it is. |
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:
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; Thus all ties should be broken in favor of the first one queue'd. per the wikipedia quote:
|
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 |
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.The text was updated successfully, but these errors were encountered: