bheap v1.0.0 BHeap.BTree

Simple binomial tree implementation.

Binomial trees are defined as follows:

A binomial tree of rank 0 is a singleton node
A binomial tree of rank r + 1 is formed by linking two binomial trees of rank r, making one tree the leftmost child of the other

We represent a node in a binomial tree as a tuple of {rank, value, children}.

Each list of children is maintained in decreasing order of rank, with elements stored in heap order. Heap order is maintained by linking trees with larger roots under trees with smaller roots.

Summary

Functions

link(tree1, tree2)

Links two binomial trees

new(value)

Creates a new binomial tree with value in it

rank(arg)

Returns the rank of a binomial tree

Functions

link(tree1, tree2)

Links two binomial trees.

The algorithm compares the values of both trees and insert’s the larger one in the rest of the smaller one, updating the rank number appropiately.

Example

iex> a = BTree.new(1)
{0, 1, []}
iex> b = BTree.new(2)
{0, 2, []}
iex> BTree.link(a, b)
{1, 1, [{0, 2, []}]}

new(value)

Creates a new binomial tree with value in it.

Example

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

rank(arg)

Returns the rank of a binomial tree.

Example

iex> a = BTree.new(1)
iex> b = BTree.new(2)
iex> c = BTree.new(2)
iex> ab = BTree.link(a, b)
iex> abc = BTree.link(ab, c)
iex> BTree.rank(abc)
2