binomial heap

some info taken from http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap20.htm

a binomial heap is a concrete data type that implements the heap using a set of binomial trees

binary heaps, binomial heaps, and fibonacci heaps are all inefficient in their support of the operation SEARCH; it can take a while to find a node with a given key. for this reason, operations such as DECREASE-KEY and DELETE that refer to a given node require a pointer to that node as part of their input. this requirement poses no problem in many applications.

binomial tree

a binomial tree is 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, (in this order)

each binomial tree in a heap obeys the min heap property

this 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.

there can be at most one binomial tree for each order, including order 0

this property implies that a binomial heap with nodes consists of at most binomial trees. 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 . for example, the decimal number 13 is 1101 in binary, , and thus a binomial heap with 13 nodes will consist of three binomial trees of orders 3, 2, and 0 (see the figure below).

a binomial heap of order 3:

this is an example binomial heap that consists of 13 nodes and 3 binomial trees

a binomial tree of order has nodes and height . the name comes from the shape: a binomial tree of order k 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.

theoretical implementation

because no operation requires random access to the root nodes of the binomial trees, the roots of the binomial trees can be stored in a linked list, ordered by increasing order of the tree. because the number of children for each node is variable, it does not work well for each node to have separate links to each of its children, as would be common in a binary tree; instead, it is possible to implement this tree using links from each node to its highest-order child in the tree, and to its sibling of the next smaller order than it. these sibling pointers can be interpreted as the next pointers in a linked list of the children of each node, but with the opposite order from the linked list of roots: from largest to smallest order, rather than vice versa. this representation allows two trees of the same order to be linked together, making a tree of the next larger order, in constant time.

each node x has a key field and contains pointers parent(x) to its parent, child(x) to its leftmost child, and sibling(x) to the sibling of x immediately to its right. if node x is a root, then parent(x) = nil. if node x has no children, then child(x) = nil, and if x is the rightmost child of its parent, then sibling(x) = nil. each node x also contains the field degree(x), which is the number of children of x.

the roots of the binomial trees within a binomial heap are organized in a linked list, which we refer to as the root list. the degrees of the roots strictly increase as we traverse the root list. in an n-node binomial heap the degrees of the roots are a subset of . the sibling field has a different meaning for roots than for nonroots. if x is a root, then sibling(x) points to the next root in the root list. (as usual, sibling(x) = nil if x is the last root in the root list.)

a given binomial heap h is accessed by the field head(h), which is simply a pointer to the first root in the root list of h. if binomial heap H has no elements, then head[h] = nil.

binomial heap creation

to make an empty binomial heap, the MAKE-BINOMIAL-HEAP procedure simply allocates and returns an object h, where head[h] = nil. the running time is .

binomial heap union

the operation of uniting two binomial heaps is used as a subroutine by most of the remaining operations. merging of binomial trees is done by comparing the keys at the roots of two trees, and the root node with the larger key will become the child of the root with the smaller key. the time complexity for finding a union is .

to perform the union of two binomial heaps, first we merge the heaps into one, such that the trees in the resulting heap would be in monotonically ascending order, then we traverse through the roots of the binomial trees, we consider the following cases where x denotes the current root:

if degree(x) is not equal to degree(next(x)), then move the pointer ahead
if degree(x) = degree(next(x)) = degree(next(next(x))) then move the pointer ahead
if degree(x) = degree(next(x)) but not equal to degree(next(next(x))), and key(x) < key(next(x)) then remove next(x) from root and attach it to x
if degree(x) = degree(next(x)) but not equal to degree(next(next(x))) and key(x) > key(next(x)) then remove x from root and attach it to next(x).

because each binomial tree in a binomial heap corresponds to a bit in the binary representation of its size, there is an analogy between the merging of two heaps and the binary addition of the sizes of the two heaps, from right-to-left. whenever a carry occurs during addition, this corresponds to a merging of two binomial trees during the merge.

each binomial tree's traversal during merge only involves roots, hence making the time taken at the biggest order and therefore the running time is .

binomial heap insert

inserting a new element to a heap can be done by creating a new heap containing only this element and then merging it with the original heap. because of the merge, a single insertion takes time . however, this can be sped up using a merge procedure that shortcuts the merge after it reaches a point where only one of the merged heaps has trees of larger order. with this speedup, across a series of consecutive insertions, the total time for the insertions is . another way of stating this is that (after logarithmic overhead for the first insertion in a sequence) each successive insert has an amortized time of (i.e. constant time) per insertion.