bheap v1.0.0 BHeap

Binomial heaps in Elixir.

For general information about them, see Wikipedia.

The collection of binomial trees satisfies the following conditions:

Each binomial tree in a heap obeys the minimum-heap property: the key of a node is greater than or equal to the key of its parent
There can only be either one or zero binomial trees for each order, including zero order

Summary

Functions

merge(bheap, bheap)

Merges two heaps

min(bheap)

Returns the minimum element of a heap

new()

Creates a new heap

new(enumerable)

Creates a new heap from a given enumerable

put(bheap, value)

Puts a new value in a heap

remove_min(bheap)

Removes the minimum element from a heap

sort(heap)

Sorts the given heap and returns a list

Functions

merge(bheap, bheap)

Merges two heaps.

Example

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

min(bheap)

Returns the minimum element of a heap.

Example

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

new()

Creates a new heap.

Example

iex> BHeap.new()
[]

new(enumerable)

Creates a new heap from a given enumerable.

Example

iex> BHeap.new([1, 2])
[{1, 1, [{0, 2, []}]}]

put(bheap, value)

Puts a new value in a heap.

Example

iex> BHeap.new() |> BHeap.put(1) |> BHeap.put(2)
[{1, 1, [{0, 2, []}]}]

remove_min(bheap)

Removes the minimum element from a heap.

Example

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

sort(heap)

Sorts the given heap and returns a list.

Example

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