PriorityQueue (priority_queue v1.1.0)

Priority Queues in Elixir

From Wikipedia: A priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to their order in the queue.

While priority queues are often implemented with heaps, they are conceptually distinct from heaps. A priority queue is an abstract concept like "a list" or "a map"; just as a list can be implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods.

In computer science, a heap is a specialized tree-based data structure that satisfies the heap property:

If A is a parent node of B, then the key of node A is ordered with respect to the key of node B, with the same ordering applying across the heap.

a) Either the keys of parent nodes are always greater than or equal to those of the children and the highest key is in the root node (this kind of heap is called max heap) b) or the keys of parent nodes are less than or equal to those of the children and the lowest key is in the root node (min heap)

The heap is one maximally efficient implementation of a Priority Queue

%% heap :: nil | {Item, Value, [heap()]}

Summary

Types

element()

key()

t()

value()

Functions

delete_min(pq)

Return new priority queue with minimum element removed

delete_min!(pq)

Return new priority queue with minimum element removed

empty?(arg1)

True iff argument is an empty priority queue

keys(pq)

Retrieve keys from priority queue as a list in sorted order (may have duplicates)

merge(pq, priority_queue)

Merge two priority queues

min(priority_queue, default \\ {nil, nil})

Return the minimum element

min!(pq)

Return the minimum element

new()

Returns new, empty priority queue

pop(pq, default \\ {nil, nil})

Returns the min item, as well as the queue without the min item

pop!(pq)

Returns the min item, as well as the queue without the min item

put(pq, arg)

Add (insert) element key,value to priority queue Pass key/value either as two arguments, or as a tuple {key,value}

put(pq, key, value \\ nil)

size(priority_queue)

Number of elements in queue

to_list(pq)

Retrieve elements from priority queue as a list in sorted order

values(pq)

Retrieve values from priority queue as a list, sorted in order of their keys

Types

element()

@type element() :: {key(), value()}

key()

@type key() :: any()

t()

@type t() :: %PriorityQueue{heap: term(), size: non_neg_integer()}

value()

@type value() :: any()

Functions

delete_min(pq)

@spec delete_min(t()) :: t()

Return new priority queue with minimum element removed

iex> [4,{8},3,{1, "first"}] |> Enum.into(PriorityQueue.new) |> PriorityQueue.delete_min |> PriorityQueue.size
3

iex> [{1, "first"}] |> Enum.into(PriorityQueue.new) |> PriorityQueue.delete_min |> PriorityQueue.delete_min |> PriorityQueue.size
0

delete_min!(pq)

@spec delete_min!(t()) :: t() | no_return()

Return new priority queue with minimum element removed

Raises a PriorityQueue.EmptyError exception if the queue is empty

iex> [4,{8},3,{1, "first"}] |> Enum.into(PriorityQueue.new) |> PriorityQueue.delete_min |> PriorityQueue.size
3

iex> [{1, "first"}] |> Enum.into(PriorityQueue.new) |> PriorityQueue.delete_min! |> PriorityQueue.delete_min! |> PriorityQueue.size
** (PriorityQueue.EmptyError) queue empty error

empty?(arg1)

@spec empty?(t()) :: boolean()

True iff argument is an empty priority queue

iex> PriorityQueue.new |> PriorityQueue.empty?
true

iex> [4,{8},3,{1, "first"}] |> Enum.into(PriorityQueue.new) |> PriorityQueue.empty?
false

keys(pq)

@spec keys(t()) :: list()

Retrieve keys from priority queue as a list in sorted order (may have duplicates)

Heap sort a list

iex> [4,{8},3,{1, "first"}] |> Enum.into(PriorityQueue.new) |> PriorityQueue.keys
[1, 3, 4, 8]

merge(pq, priority_queue)

@spec merge(t(), t()) :: t()

Merge two priority queues

iex> PriorityQueue.merge( Enum.into([4,{8}], PriorityQueue.new), Enum.into([3,{1, "first"}], PriorityQueue.new)) |> PriorityQueue.to_list
[{1, "first"}, {3, nil}, {4, nil}, {8, nil}]

min(priority_queue, default \\ {nil, nil})

@spec min(t(), element()) :: element()

Return the minimum element

If the queue is empty, returns the default value ({nil, nil} if no default value)

iex> [4,{8},3,{1, "first"}] |> Enum.into(PriorityQueue.new) |> PriorityQueue.min
{1, "first"}

iex> PriorityQueue.new |> PriorityQueue.min({:empty, nil})
{:empty, nil}

min!(pq)

@spec min!(t()) :: element() | no_return()

Return the minimum element

Raises a PriorityQueue.EmptyError exception if the queue is empty

iex> [4,{8},3,{1, "first"}] |> Enum.into(PriorityQueue.new) |> PriorityQueue.min!
{1, "first"}

iex> PriorityQueue.new |> PriorityQueue.min!
** (PriorityQueue.EmptyError) queue empty error

new()

Returns new, empty priority queue

pop(pq, default \\ {nil, nil})

@spec pop(t(), element()) :: {element(), t()}

Returns the min item, as well as the queue without the min item

If the queue is empty, returns the default value ({nil, nil} if no default value)

Equivalent to: {min(pq), delete_min(pq)}

iex> [4,{8},3,{1, "first"}] |> Enum.into(PriorityQueue.new) |> PriorityQueue.pop |> elem(0)
{1, "first"}

iex> [4,{8},3,{1, "first"}] |> Enum.into(PriorityQueue.new) |> PriorityQueue.pop |> elem(1) |> PriorityQueue.to_list
[{3, nil}, {4, nil}, {8, nil}]

iex> [{1, "first"}] |> Enum.into(PriorityQueue.new) |> PriorityQueue.pop |> elem(1) |> PriorityQueue.pop({:empty, nil}) |> elem(0)
{:empty, nil}

iex> PriorityQueue.new |> PriorityQueue.pop({:empty, nil}) |> elem(0)
{:empty, nil}

pop!(pq)

@spec pop!(t()) :: {element(), t()} | no_return()

Returns the min item, as well as the queue without the min item

Raises a PriorityQueue.EmptyError exception if the queue is empty

Equivalent to: {min!(pq), delete_min!(pq)}

iex> [4,{8},3,{1, "first"}] |> Enum.into(PriorityQueue.new) |> PriorityQueue.pop! |> elem(0)
{1, "first"}

iex> [{1, "first"}] |> Enum.into(PriorityQueue.new) |> PriorityQueue.pop! |> elem(1) |> PriorityQueue.pop! |> elem(0)
** (PriorityQueue.EmptyError) queue empty error

iex> PriorityQueue.new |> PriorityQueue.pop! |> elem(0)
** (PriorityQueue.EmptyError) queue empty error

put(pq, arg)

@spec put(
  t(),
  {key(), value()}
) :: t()

Add (insert) element key,value to priority queue Pass key/value either as two arguments, or as a tuple {key,value}

iex> PriorityQueue.new |> PriorityQueue.put(1) |> PriorityQueue.to_list
[{1, nil}]

iex> PriorityQueue.new |> PriorityQueue.put(1, "first") |> PriorityQueue.to_list
[{1, "first"}]

iex> PriorityQueue.new |> PriorityQueue.put({1, "first"}) |> PriorityQueue.to_list
[{1, "first"}]

put(pq, key, value \\ nil)

@spec put(t(), key(), value() | none()) :: t()

size(priority_queue)

@spec size(t()) :: non_neg_integer()

Number of elements in queue

iex> [4,{8},3,{1, "first"}] |> Enum.into(PriorityQueue.new) |> PriorityQueue.size
4

to_list(pq)

@spec to_list(t()) :: list()

Retrieve elements from priority queue as a list in sorted order

iex> [4,{8},3,{1, "first"}] |> Enum.into(PriorityQueue.new) |> PriorityQueue.to_list
[{1, "first"}, {3, nil}, {4, nil}, {8, nil}]

values(pq)

@spec values(t()) :: list()

Retrieve values from priority queue as a list, sorted in order of their keys

iex> [4,{8, "last"},3,{1, "first"}] |> Enum.into(PriorityQueue.new) |> PriorityQueue.values
["first", nil, nil, "last"]