View Source PriorityQueue (hologram v0.2.0)

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.

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.

Types

t()

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

Functions

new()

@spec new() :: t()

Create a new priority queue

peek(pq)

@spec 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)

@spec 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)

@spec 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}