# `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.

# `t`

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

# `new`

```elixir
@spec new() :: t()
```

Create a new priority queue

# `peek`

```elixir
@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`

```elixir
@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`

```elixir
@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}

---

*Consult [api-reference.md](api-reference.md) for complete listing*