libgraph v0.16.0

PriorityQueue (libgraph v0.16.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.

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

Link to this type

t()

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

Link to this section Functions

Link to this function

new()

@spec new() :: t()

Create a new priority queue

Link to this function

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

 Example 

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

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

 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
Link to this function

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

 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}