libgraph v0.13.3 PriorityQueue

This module defines a priority queue datastructure, intended for use with graphs, as it prioritizes lower priority values over higher priority values (ideal for priorities based on edge weights, etc.).

This implementation makes use of :gb_trees under the covers. It is also very fast, even for a very large number of distinct priorities. Other priority queue implementations I’ve looked at are either slow when working with large numbers of priorities, or restrict themselves to a specific number of allowed priorities, which is why I’ve ended up writing my own.

Link to this section Summary

Types

t()

Functions

new()

Create a new priority queue

peek(pq)

This function returns the value at the top of the queue. If the queue is empty, :empty is returned, otherwise {:value, term}. This function does not modify the queue

pop(pq)

Pops an element from the queue with the lowest integer value priority

push(pq, term, priority)

Push a new element into the queue with the given priority

Link to this section Types

t()

t() :: %PriorityQueue{
  priorities: :gb_trees.tree(integer(), :queue.queue(term()))
}

Link to this section Functions

new()

new() :: t()

Create a new priority queue

peek(pq)

peek(t()) :: :empty | {:value, term()}

This function returns the value at the top of the queue. If the queue is empty, :empty is returned, otherwise {:value, term}. This function does not modify the queue.

Example

iex> pq = PriorityQueue.new |> PriorityQueue.push(:foo, 1)
...> {:value, :foo} = PriorityQueue.peek(pq)
...> {{:value, val}, _} = PriorityQueue.pop(pq)
...> val
:foo

pop(pq)

pop(t()) :: {:empty, t()} | {{:value, term()}, t()}

Pops an element from the queue with the lowest integer value priority.

Returns {:empty, PriorityQueue.t} if there are no elements left to dequeue.

Returns {{:value, term}, PriorityQueue.t} if the dequeue is successful

This is equivalent to the extract-min operation described in priority queue theory.

Example

iex> pq = PriorityQueue.new
...> pq = Enum.reduce(Enum.shuffle(0..4), pq, fn i, pq -> PriorityQueue.push(pq, ?a+i, i) end)
...> {{:value, ?a}, pq} = PriorityQueue.pop(pq)
...> {{:value, ?b}, pq} = PriorityQueue.pop(pq)
...> {{:value, ?c}, pq} = PriorityQueue.pop(pq)
...> {{:value, ?d}, pq} = PriorityQueue.pop(pq)
...> {{:value, ?e}, pq} = PriorityQueue.pop(pq)
...> {result, _} = PriorityQueue.pop(pq)
...> result
:empty

push(pq, term, priority)

push(t(), term(), integer() | float()) :: t()

Push a new element into the queue with the given priority.

Priorities must be integer or float values.

Example

iex> pq = PriorityQueue.new
...> pq = PriorityQueue.push(pq, :foo, 1)
...> {result, _} = PriorityQueue.pop(pq)
...> result
{:value, :foo}

iex> pq = PriorityQueue.new
...> pq = PriorityQueue.push(pq, :foo, 1)
...> {{:value, :foo}, pq} = PriorityQueue.pop(pq)
...> pq = PriorityQueue.push(pq, :bar, 1)
...> {result, _} = PriorityQueue.pop(pq)
...> result
{:value, :bar}