How to change the priority of an item in a DataStructures.PriorityQueue?

General Usage
,
1

Can I remove an item from a DataStructures.PriorityQueue, other than the lowest priority?
Alternatively, can I change the priority of an item inside a PriorityQueue?

2

I’ll just point out that you can do both of these operations plus others using SortedDict or SortedMultiDict (use the latter if keys can have multiplicity>1), which are also in the DataStructures package.

3

Thanks. But I would like to consider the simplest structure that meets my requirements. Are you saying that PriorityQueue does not support modification of priorities?

4

I believe you can do the operations you want with PriorityQueue, but I haven’t tested it. To remove an arbitrary item, use dequeue_pair!(pq, k), where pq is the queue and k is the key. To change a priority, use pq[k]=v, where v is the new priority and k is the key whose priority you wish to change.

1 Like
5

You can change the weights in a PQ as follows:

julia> P = PriorityQueue(Char, Int)
DataStructures.PriorityQueue{Char,Int64,Base.Order.ForwardOrdering} with 0 entries

julia> enqueue!(P, 'a', 1)
DataStructures.PriorityQueue{Char,Int64,Base.Order.ForwardOrdering} with 1 entry:
  'a' => 1

julia> enqueue!(P, 'b', 2)
DataStructures.PriorityQueue{Char,Int64,Base.Order.ForwardOrdering} with 2 entries:
  'b' => 2
  'a' => 1

julia> enqueue!(P, 'c', 3)
DataStructures.PriorityQueue{Char,Int64,Base.Order.ForwardOrdering} with 3 entries:
  'b' => 2
  'a' => 1
  'c' => 3

julia> P['a'] = 4
4

julia> P
DataStructures.PriorityQueue{Char,Int64,Base.Order.ForwardOrdering} with 3 entries:
  'b' => 2
  'a' => 4
  'c' => 3

julia> dequeue!(P)
'b': ASCII/Unicode U+0062 (category Ll: Letter, lowercase)

julia> dequeue!(P)
'c': ASCII/Unicode U+0063 (category Ll: Letter, lowercase)

julia> dequeue!(P)
'a': ASCII/Unicode U+0061 (category Ll: Letter, lowercase)
1 Like
6

Yes, your suggestions work, I just tested them. Thanks.