PriorityQueue allowing multiple elements with same priority

[Tomas Lycken]

I tried this today:

immutable State
    a::Int
    b::Int
end

import Base.Collections: PriorityQueue, enqueue!, dequeue!, peek

pq = PriorityQueue(Int,Int)

enqueue!(pq, State(5,3), 4)
enqueue!(pq, State(5,3), 2)

but it fails with the error

LoadError: ArgumentError: PriorityQueue keys must be unique

I assume this is because the states are immutable, and thus compare equal if all their values compare equal. Is there a way to make a priority queue insert the same state on several priorities, i.e. to support my example above?

// T

​

[Kenta Sato]

The priority queue in Base is different from priority queues in other languages.

I think you can use a plain priority queue (or heap) defined the DataStructures.jl package.

To pair priority and state, `priority => state` would be helpful. This paired values are ordered by the first element (priority) and then the second element (state). So you can push and pop according to the priority.

Here is an example:

julia> Base.isless(s1::State, s2::State) = isless(s1.a, s1.a) || (s1.a == s2.b && isless(s
1.a, s2.b))
isless (generic function with 32 methods)


julia> h = binary_minheap(Pair{Int,State})
DataStructures.BinaryHeap{Pair{Int64,State},DataStructures.LessThan}(DataStructures.LessTh
an(),Pair{Int64,State}[])


julia> push!(h, 4 => State(5, 3))


julia> push!(h, 2 => State(5, 3))


julia> top(h)
2=>State(5,3)


julia> pop!(h)
2=>State(5,3)


julia> top(h)
4=>State(5,3)

[Kenta Sato]

Sorry, I meant:

Base.isless(s1::State, s2::State) = isless(s1.a, s2.a) || (s1.a == s2.a && isless(s1.b, s2.b))