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
— TypePriorityQueue{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
Usage
The PriorityQueue
type implements the following methods:
delete!(pd::PriorityQueue, key)
empty!(pd::PriorityQueue)
first(pd::PriorityQueue)
haskey(pd::PriorityQueue, key)
isempty(pd::PriorityQueue)
length(pd::PriorityQueue)
popfirst!(pd::PriorityQueue)
push!(pd::PriorityQueue)
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!
— Methoddelete!(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
Base.empty!
— Methodempty!(pq::PriorityQueue)
Reset priority queue pq
.
Base.first
— Methodfirst(pq::PriorityQueue)
Return the lowest priority pair (k
, v
) from pq
without removing it from the priority queue.
Base.haskey
— Methodhaskey(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
Base.isempty
— Methodisempty(pq::PriorityQueue)
Verify if priority queue pq
is empty.
Base.length
— Methodlength(pq::PriorityQueue)
Return the number of pairs (k
, v
) in the priority queue pq
.
Base.popfirst!
— Methodpopfirst!(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
Base.push!
— Methodpush!(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