Heap.LeftiestTree (Heap v1.0.0) View Source

A leftiest tree/heap implemtation with customizable priority and any type of item.

This tree always enforces the smallest priority at the top node, and the left path of tree is higher than right. See https://en.wikipedia.org/wiki/Leftist_tree for algorithm details.

Link to this section Summary

Functions

empty?(tree)

Returns true if the leftest tree is empty.

merge(tree1, tree2)

Merges two leftiest trees into a leftiest tree.

pop(tree)

Removes the topest node of tree, rebalances the tree, and returns. Do nothing if tree is empty.

single(item)

Returns a single node leftest tree, with item and use this item as priority.

single(item, priority)

Returns a single node leftiest tree, with item and priority.

size(tree)

Returns the number of elements in tree.

to_list(tree)

Returns the list of %{priority: ..., item:, ...} ordered by priority descendingly.

top(tree)

Returns the top node of tree. If the tree is empty, returns {:error, "empty tree"}, otherwise returns {:ok, %{priority: ..., item: ...}}

Link to this section Functions

empty?(tree)

Specs

empty?(atom() | %{:item => any(), optional(any()) => any()}) :: boolean()

Returns true if the leftest tree is empty.

NOTE: the nil is an empty leftest tree also.

Examples

iex>  Heap.LeftiestTree.single(1)
...>    |>  Heap.LeftiestTree.empty?
false

merge(tree1, tree2)

Merges two leftiest trees into a leftiest tree.

Examples

iex> nil
...>  |> Heap.LeftiestTree.merge(Heap.LeftiestTree.single(1))
...>  |> Heap.LeftiestTree.merge(nil)
...>  |> Heap.LeftiestTree.merge(Heap.LeftiestTree.single(-1))
...>  |> Heap.LeftiestTree.to_list
[%{item: 1, priority: 1}, %{item: -1, priority: -1}]

pop(tree)

Removes the topest node of tree, rebalances the tree, and returns. Do nothing if tree is empty.

Examples

iex> Heap.LeftiestTree.single(1)
...>   |> Heap.LeftiestTree.pop
...>   |> Heap.LeftiestTree.empty?
true

iex> Heap.LeftiestTree.single(1)
...>   |> Heap.LeftiestTree.pop
...>   |> Heap.LeftiestTree.pop
nil

single(item)

Specs

single(any()) :: %Heap.LeftiestTree{
  item: any(),
  left: nil,
  priority: any(),
  right: nil,
  s_value: 1
}

Returns a single node leftest tree, with item and use this item as priority.

Examples

iex>  Heap.LeftiestTree.single(1)
...>    |>  Heap.LeftiestTree.size
1

single(item, priority)

Specs

single(any(), any()) :: %Heap.LeftiestTree{
  item: any(),
  left: nil,
  priority: any(),
  right: nil,
  s_value: 1
}

Returns a single node leftiest tree, with item and priority.

Examples

iex> Heap.LeftiestTree.single(1, 1)
...>   |> Heap.LeftiestTree.size
1

size(tree)

Returns the number of elements in tree.

Examples

iex> nil |> Heap.LeftiestTree.size
0

iex> Heap.LeftiestTree.single(1) |> Heap.LeftiestTree.size
1

to_list(tree)

Returns the list of %{priority: ..., item:, ...} ordered by priority descendingly.

Examples

iex> Heap.LeftiestTree.single(-10)
...>  |> Heap.LeftiestTree.merge(Heap.LeftiestTree.single(1))
...>  |> Heap.LeftiestTree.merge(Heap.LeftiestTree.single(3))
...>  |> Heap.LeftiestTree.merge(Heap.LeftiestTree.single(-1))
...>  |> Heap.LeftiestTree.to_list
[%{item: 3, priority: 3}, %{item: 1, priority: 1}, %{item: -1, priority: -1}, %{item: -10, priority: -10}]

top(tree)

Returns the top node of tree. If the tree is empty, returns {:error, "empty tree"}, otherwise returns {:ok, %{priority: ..., item: ...}}

Examples

iex> Heap.LeftiestTree.single(1)
...>   |> Heap.LeftiestTree.top
{:ok, %{priority: 1, item: 1}}

iex> Heap.LeftiestTree.single(1)
...>   |> Heap.LeftiestTree.pop
...>   |> Heap.LeftiestTree.top
{:error, "empty tree"}