priority_queue v1.0.0 PriorityQueue

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(priority_queue)

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(priority_queue1, priority_queue2)

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(priority_queue, 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(priority_queue, arg)

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

put(priority_queue, 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 :: {key, value}

key :: any

t :: %PriorityQueue{heap: term, size: non_neg_integer}

value :: any

Functions

delete_min(priority_queue)

Specs

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)

Specs

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)

Specs

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)

Specs

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(priority_queue1, priority_queue2)

Specs

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})

Specs

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)

Specs

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(priority_queue, default \\ {nil, nil})

Specs

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)

Specs

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(priority_queue, arg)

Specs

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(priority_queue, key, value \\ nil)

Specs

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

size(priority_queue)

Specs

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)

Specs

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)

Specs

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"]