Binomial Heap - Binomial Tree

A binomial heap is implemented as a collection of binomial trees (compare with a binary heap, which has a shape of a single binary tree). A binomial tree is defined recursively:

• A binomial tree of order 0 is a single node
• A binomial tree of order k has a root node whose children are roots of binomial trees of orders k−1, k−2, ..., 2, 1, 0 (in this order).

A binomial tree of order k has 2k nodes, height k.

Because of its unique structure, a binomial tree of order k can be constructed from two trees of order k−1 trivially by attaching one of them as the leftmost child of root of the other one. This feature is central to the merge operation of a binomial heap, which is its major advantage over other conventional heaps.

The name comes from the shape: a binomial tree of order has nodes at depth . (See Binomial coefficient.)