lheap v1.0.0 LHeap

Leftist heaps in Elixir.

For general information about them, see Wikipedia.

Leftist heap elements are represented by a three element tuple of the form:

{{s-value, value}, left, right}

Where:

s-value is the distance from that node to the nearest leaf of the extended binary tree representation
value, is the actual value of the node
left and right are other heaps

Summary

Functions

merge(lheap1, lheap2)

Merges two heaps

min(arg)

Returns the minimum element of a heap

new()

Creates a new, empty heap

new(enumerable)

Creates a new heap from a given enumerable

put(lheap, value)

Puts a new value in a heap

remove_min(arg)

Removes the minimum element from a heap

sort(heap)

Sorts the given heap and returns a list

Functions

merge(lheap1, lheap2)

Merges two heaps.

Example

iex> heap1 = LHeap.new([2, 4, 6])
iex> heap2 = LHeap.new([1, 3, 5])
iex> LHeap.merge(heap1, heap2)
{{2, 1}, {{2, 2}, {{1, 4}, {}, {}}, {{1, 5}, {{1, 6}, {}, {}}, {}}},
  {{1, 3}, {}, {}}}

min(arg)

Returns the minimum element of a heap.

Example

iex> LHeap.new([10, 1, 7]) |> LHeap.min()
1

new()

Creates a new, empty heap.

Example

iex> LHeap.new()
{}

new(enumerable)

Creates a new heap from a given enumerable.

Example

iex> LHeap.new([4, 3, 8])
{{2, 3}, {{1, 4}, {}, {}}, {{1, 8}, {}, {}}}

put(lheap, value)

Puts a new value in a heap.

Example

iex> LHeap.new() |> LHeap.put(10) |> LHeap.put(1) |> LHeap.put(5) |> LHeap.put(7)
{{2, 1}, {{1, 10}, {}, {}}, {{1, 5}, {{1, 7}, {}, {}}, {}}}

remove_min(arg)

Removes the minimum element from a heap.

Example

iex> LHeap.new([10, 1, 7]) |> LHeap.remove_min()
{{1, 7}, {{1, 10}, {}, {}}, {}}

sort(heap)

Sorts the given heap and returns a list.

Example

iex> heap1 = LHeap.new([2, 4, 6, 8, 10])
iex> heap2 = LHeap.new([1, 3, 5, 7, 9])
iex> LHeap.merge(heap1, heap2) |> LHeap.sort()
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]