Binomial heap

In computer science, a binomial heap is a data structure that acts as a priority queue but also allows pairs of heaps to be merged. It is important as an implementation of the mergeable heap abstract data type (also called meldable heap), which is a priority queue supporting merge operation. It is implemented as a heap similar to a binary heap but using a special tree structure that is different from the complete binary trees used by binary heaps. Binomial heaps were invented in 1978 by Jean Vuillemin. A binomial heap is implemented as a set of binomial trees (compare with a binary heap, which has a shape of a single binary tree), which are defined recursively as follows: A binomial tree of order 0 is a single node A binomial tree of order has a root node whose children are roots of binomial trees of orders , , ..., 2, 1, 0 (in this order). A binomial tree of order has nodes, and height . The name comes from the shape: a binomial tree of order has nodes at depth , a binomial coefficient. Because of its structure, a binomial tree of order can be constructed from two trees of order by attaching one of them as the leftmost child of the root of the other tree. This feature is central to the merge operation of a binomial heap, which is its major advantage over other conventional heaps. A binomial heap is implemented as a set of binomial trees that satisfy the binomial heap properties: 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 be at most one binomial tree for each order, including zero order. The first property ensures that the root of each binomial tree contains the smallest key in the tree. It follows that the smallest key in the entire heap is one of the roots. The second property implies that a binomial heap with nodes consists of at most binomial trees, where is the binary logarithm. The number and orders of these trees are uniquely determined by the number of nodes : there is one binomial tree for each nonzero bit in the binary representation of the number .