# 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

## Functions

Return new priority queue with minimum element removed

Return new priority queue with minimum element removed

True iff argument is an empty priority queue

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

Merge two priority queues

Return the minimum element

Return the minimum element

Returns new, empty priority queue

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

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

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

Number of elements in queue

Retrieve elements from priority queue as a list in sorted order

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