# I want to use a PriorityQueue equivalent with duplicate keys

**URL:** <https://discourse.julialang.org/t/i-want-to-use-a-priorityqueue-equivalent-with-duplicate-keys/107534>\
**Category:** General Usage\
**Tags:** question, data\_structures\
**Created:** [December 12, 2023, 11:06pm UTC](https://discourse.julialang.org/t/i-want-to-use-a-priorityqueue-equivalent-with-duplicate-keys/107534 "2023-12-12T23:06:33Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![Lee\_Phillips](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lee_phillips/32/203984_2.png) [@Lee\_Phillips](https://discourse.julialang.org/u/Lee_Phillips)\
**Post date:** [December 12, 2023, 11:06pm UTC](https://discourse.julialang.org/t/i-want-to-use-a-priorityqueue-equivalent-with-duplicate-keys/107534/1 "2023-12-12T23:06:33Z")

</div>

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
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>

```

---

<div class="post-metadata">

**Author:** ![Stephen\_Vavasis](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stephen_vavasis/32/3389_2.png) [@Stephen\_Vavasis](https://discourse.julialang.org/u/Stephen_Vavasis)\
**Post date:** [December 13, 2023, 1:18am UTC](https://discourse.julialang.org/t/i-want-to-use-a-priorityqueue-equivalent-with-duplicate-keys/107534/2 "2023-12-13T01:18:35Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Lee\_Phillips](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lee_phillips/32/203984_2.png) [@Lee\_Phillips](https://discourse.julialang.org/u/Lee_Phillips)\
**Post date:** [December 13, 2023, 11:12pm UTC](https://discourse.julialang.org/t/i-want-to-use-a-priorityqueue-equivalent-with-duplicate-keys/107534/3 "2023-12-13T23:12:04Z")

</div>

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](https://juliacollections.github.io/DataStructures.jl/v0.9/sorted_containers.html#Inserting-and-Deleting-in-Sorted-Containers-1)) **!pop** is meant to remove and return the given key

```julia
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>

```

---

<div class="post-metadata">

**Author:** ![Stephen\_Vavasis](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stephen_vavasis/32/3389_2.png) [@Stephen\_Vavasis](https://discourse.julialang.org/u/Stephen_Vavasis)\
**Post date:** [December 13, 2023, 11:54pm UTC](https://discourse.julialang.org/t/i-want-to-use-a-priorityqueue-equivalent-with-duplicate-keys/107534/4 "2023-12-13T23:54:50Z")

</div>

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
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"

```

---

<div class="post-metadata">

**Author:** ![Lee\_Phillips](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lee_phillips/32/203984_2.png) [@Lee\_Phillips](https://discourse.julialang.org/u/Lee_Phillips)\
**Post date:** [December 14, 2023, 2:09am UTC](https://discourse.julialang.org/t/i-want-to-use-a-priorityqueue-equivalent-with-duplicate-keys/107534/5 "2023-12-14T02:09:08Z")

</div>

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