# 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

Returns true if the leftest tree is empty.

Merges two leftiest trees into a leftiest tree.

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

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

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

Returns the number of elements in tree.

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

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

# empty?(tree)

View Source

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

View Source

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)

View Source

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)

View Source

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

View Source

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

View Source

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)

View Source

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)

View Source

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