GitHub

Priority Queue

The PriorityQueue type provides a basic priority queue implementation allowing for arbitrary key and priority types. Multiple identical keys are not permitted, but the priority of existing keys can be changed efficiently.

Constructors

DataStructures.PriorityQueue — Type
PriorityQueue{K, V}([ord])

Construct a new PriorityQueue, with keys of type K and values/priorities of type V. If an order is not given, the priority queue is min-ordered using the default comparison for V.

A PriorityQueue acts like a Dict, mapping values to their priorities. New elements are added using push! and retrieved using popfirst! or popat! based on their priority.

Parameters

K::Type Data type for the keys

V::Type Data type for the values/priorities

ord::Base.Ordering Priority queue ordering

Examples

julia> PriorityQueue(Base.Order.Forward, "a" => 2, "b" => 3, "c" => 1)
PriorityQueue{String, Int64, Base.Order.ForwardOrdering} with 3 entries:
  "c" => 1
  "a" => 2
  "b" => 3
source

Usage

The PriorityQueue type implements the following methods:

Note

PriorityQueue also behaves similarly to a Dict in that keys can be inserted and priorities accessed or changed using indexing notation.

Examples:

julia> pq = PriorityQueue();

julia> # Insert keys with associated priorities
       pq["a"] = 10; pq["b"] = 5; pq["c"] = 15; pq
PriorityQueue{Any, Any, Base.Order.ForwardOrdering} with 3 entries:
  "b" => 5
  "a" => 10
  "c" => 15

julia> # Change the priority of an existing key
       pq["a"] = 0; pq
PriorityQueue{Any, Any, Base.Order.ForwardOrdering} with 3 entries:
  "a" => 0
  "b" => 5
  "c" => 15

It is also possible to iterate over the priorities and elements of the queue in sorted order.

julia> pq = PriorityQueue("a" => 2, "b" => 1, "c" => 3)
PriorityQueue{String, Int64, Base.Order.ForwardOrdering} with 3 entries:
  "b" => 1
  "a" => 2
  "c" => 3

julia> for priority in values(pq)
           println(priority)
       end
1
2
3

julia> for element in keys(pq)
           println(element)
       end
b
a
c

julia> for (element, priority) in pq
           println("$element $priority")
       end
b 1
a 2
c 3
Base.delete! — Method
delete!(pq::PriorityQueue, key)

Delete the mapping for the given key in a priority queue pq and return the priority queue.

Examples

julia> q = PriorityQueue(Base.Order.Forward, "a" => 2, "b" => 3, "c" => 1)
PriorityQueue{String, Int64, Base.Order.ForwardOrdering} with 3 entries:
  "c" => 1
  "a" => 2
  "b" => 3
julia> delete!(q, "b")
PriorityQueue{String, Int64, Base.Order.ForwardOrdering} with 2 entries:
  "c" => 1
  "a" => 2
source
Base.first — Method
first(pq::PriorityQueue)

Return the lowest priority pair (k, v) from pq without removing it from the priority queue.

source
Base.haskey — Method
haskey(pq::PriorityQueue, key)

Verify if priority queue pq has key in its keys.

Example

julia> pq = PriorityQueue("a" => 1, "b" => 2, "c" => 3)
PriorityQueue{String, Int64, Base.Order.ForwardOrdering} with 3 entries:
  "a" => 1
  "b" => 2
  "c" => 3

julia> haskey(pq, "a")
true

julia> haskey(pq, "e")
false
source
Base.isempty — Method
isempty(pq::PriorityQueue)

Verify if priority queue pq is empty.

source
Base.length — Method
length(pq::PriorityQueue)

Return the number of pairs (k, v) in the priority queue pq.

source
Base.popfirst! — Method
popfirst!(pq::PriorityQueue)

Remove and return the lowest priority key and value from a priority queue pq as a pair.

Examples

julia> a = PriorityQueue(Base.Order.Forward, "a" => 2, "b" => 3, "c" => 1)
PriorityQueue{String, Int64, Base.Order.ForwardOrdering} with 3 entries:
  "c" => 1
  "a" => 2
  "b" => 3

julia> popfirst!(a)
"c" => 1

julia> a
PriorityQueue{String, Int64, Base.Order.ForwardOrdering} with 2 entries:
  "a" => 2
  "b" => 3
source
Base.push! — Method
push!(pq::PriorityQueue{K,V}, pair::Pair{K,V}) where {K,V}

Insert the a key k into a priority queue pq with priority v.

Examples

julia> a = PriorityQueue("a" => 1, "b" => 2, "c" => 3, "e" => 5)
PriorityQueue{String, Int64, Base.Order.ForwardOrdering} with 4 entries:
  "a" => 1
  "b" => 2
  "c" => 3
  "e" => 5

julia> push!(a, "d" => 4)
PriorityQueue{String, Int64, Base.Order.ForwardOrdering} with 5 entries:
  "a" => 1
  "b" => 2
  "c" => 3
  "d" => 4
  "e" => 5
source