I want to use a PriorityQueue equivalent with duplicate keys

General Usage
,
1

Hey All

I have some code pasted below making use of PriorityQueue from DataStructures package

I’d like to store key value pairs in a sorted manner to easily retrieve the lowest key from the set.

I need to be able to use duplicated key values

PriorityQueue from DataStructures package does not allow for duplicated key values

I understand there is a number of heap functions and data structures that do allow for duplicated key values

But after a few hours of searching I can not find a clear example showing how to use these heap functions or data structures

What few clear examples I can find seem to not allow for key value pair storage

Please can you clearly write an example showing how to store integer keys and string values in a sorted manner

Thank you very much for the help

julia> using DataStructures

julia> my_q = PriorityQueue{Int64, String}()
PriorityQueue{Int64, String, Base.Order.ForwardOrdering}()

julia> enqueue!(my_q, 1, "First one")
PriorityQueue{Int64, String, Base.Order.ForwardOrdering} with 1 entry:
  1 => "First one"

julia> enqueue!(my_q, 4, "Fourth one")
PriorityQueue{Int64, String, Base.Order.ForwardOrdering} with 2 entries:
  1 => "First one"
  4 => "Fourth one"

julia> enqueue!(my_q, 1, "first one again")
ERROR: ArgumentError: PriorityQueue keys must be unique
Stacktrace:
 [1] enqueue!(pq::PriorityQueue{Int64, String, Base.Order.ForwardOrdering}, pair::Pair{Int64, String})
   @ DataStructures C:\Users\Lee.Phillips\.julia\packages\DataStructures\MKv4P\src\priorityqueue.jl:231
 [2] enqueue!(pq::PriorityQueue{Int64, String, Base.Order.ForwardOrdering}, key::Int64, value::String)
   @ DataStructures C:\Users\Lee.Phillips\.julia\packages\DataStructures\MKv4P\src\priorityqueue.jl:246
 [3] top-level scope
   @ REPL[5]:1

julia>
2

Did you try SortedMultiDict, which is also in the DataStructures package?

1 Like
3

I tried using SortedMultiDict

It seems to work a bit better, but i need a little bit more help on how to actually remove the first key

The code pasted below shows my issues.

As far as I can tell from the documentation (Here) !pop is meant to remove and return the given key

julia> using DataStructures

julia> new_queue = SortedMultiDict{Int64, String}()
SortedMultiDict(Base.Order.ForwardOrdering(),)

julia> push!(new_queue, 1=>"first one")
SortedMultiDict(Base.Order.ForwardOrdering(),1 => first one)

julia> push!(new_queue, 4=>"fourth one")
SortedMultiDict(Base.Order.ForwardOrdering(),1 => first one, 4 => fourth one)

julia> push!(new_queue, 1=>"first one again")
SortedMultiDict(Base.Order.ForwardOrdering(),1 => first one, 1 => first one again, 4 => fourth one)

julia> new_queue
SortedMultiDict(Base.Order.ForwardOrdering(),1 => first one, 1 => first one again, 4 => fourth one)

julia> length(new_queue)
3

julia> first(new_queue)
1 => "first one"

julia> pop!(new_queue, 1)
ERROR: MethodError: no method matching pop!(::SortedMultiDict{Int64, String, Base.Order.ForwardOrdering}, ::Int64)

Closest candidates are:
  pop!(::IdDict{K, V}, ::Any) where {K, V}
   @ Base iddict.jl:124
  pop!(::IdDict{K, V}, ::Any, ::Any) where {K, V}
   @ Base iddict.jl:112
  pop!(::SortedSet, ::Any)
   @ DataStructures C:\Users\Lee.Phillips\.julia\packages\DataStructures\MKv4P\src\sorted_set.jl:240
  ...

Stacktrace:
 [1] top-level scope
   @ REPL[49]:1

julia>
4

The documentation cited in your message says that pop!(sc,k) is available for SortedSet and SortedDict but not SortedMultiDict. This is because a single key may correspond to many entries in a SortedMultiDict. If you want the very first data item (according to the sort order of the keys, and, secondarily, according to the insertion order of equal keys) in the SortedMultiDict s, then you can use startof(s) to obtain a semitoken pointing to that item. The semitoken can the be dereferenced with deref and/or deleted with delete! if you want to remove the item (as pop does).

If you want all the data items associated with a certain key, not necessarily the first one, then use searchequalrange. See the trace below. Note the double parentheses in deref and delete!.

julia> using DataStructures

julia> s = SortedMultiDict(1=>"one", 4=>"four", 1=>"one again")
SortedMultiDict(Base.Order.ForwardOrdering(),1 => one, 1 => one again, 4 => four)

julia> first(s)
1 => "one"

julia> p = startof(s)
DataStructures.Tokens.IntSemiToken(3)

julia> deref((s,p))
1 => "one"

julia> delete!((s,p))

julia> s
SortedMultiDict(Base.Order.ForwardOrdering(),1 => one again, 4 => four)

julia> push!(s, 1=>"once more")
SortedMultiDict(Base.Order.ForwardOrdering(),1 => one again, 1 => once more, 4 => four)

julia> (e,f) = searchequalrange(s, 1)
(DataStructures.Tokens.IntSemiToken(5), DataStructures.Tokens.IntSemiToken(3))

julia> s[e]
"one again"

julia> s[f]
"once more"
2 Likes
5

Thanks very much for the help

This is exactly the information I was trying to find from the DataStructures documentation

I was just naive and didn’t understand what a SemiToken was