Binomial heaps: A binomial heap H is a set of binomial trees that satisfies the following binomial-heap properties.
Each binomial tree in H obeys the min-heap property: the key of a node is greater than or equal to the key of its parent. We say that each such tree is min-heap-ordered.
For any nonnegative integer k, there is at most one binomial tree in H whose root has degree k.
The first property tells us that the root of a min-heap-ordered tree contains the smallest key in the tree.
The second property implies that an n-node binomial heap H consists of at most ⌊lgn⌋ 1 binomial trees. To see why, observe that the binary representation of n has ⌊lg n⌋ 1 bits, say 〈b⌊lg n⌋, b⌊lg n⌋-1, ..., b0〉, so that . By property 1 of Lemma 19.1, therefore, binomial tree Bi appears in H if and only if bit bi = 1. Thus, binomial heap H contains at most ⌊lg n⌋ 1 binomial trees.
Figure 19.3(a) shows a binomial heap H with 13 nodes. The binary representation of 13 is 〈1101〉, and H consists of min-heap-ordered binomial trees B3, B2, and B0, having 8, 4, and 1 nodes respectively, for a total of 13 nodes.
As shown in Figure 19.3(b), each binomial tree within a binomial heap is stored in the left-child, right-sibling representation of Section 10.4. Each node has a key field and any other satellite information required by the application. In addition, each node x contains pointers p[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 p[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.
As Figure 19.3 also shows, 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. By the second binomial-heap property, in an n-node binomial heap the degrees of the roots are a subset of {0, 1, ..., ⌊lg n⌋}. 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.