SKEDSOFT

Design Analysis Of Algorithm

Binomial heaps: A binomial heap H is a set of binomial trees that satisfies the following binomial-heap properties.

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

  2. 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 blg n, blg 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.

Figure 19.3: A binomial heap H with n = 13 nodes. (a) The heap consists of binomial trees B0, B2, and B3, which have 1, 4, and 8 nodes respectively, totaling n = 13 nodes. Since each binomial tree is min-heap-ordered, the key of any node is no less than the key of its parent. Also shown is the root list, which is a linked list of roots in order of increasing degree. (b) A more detailed representation of binomial heap H . Each binomial tree is stored in the left-child, right-sibling representation, and each node stores its degree.

Representing binomial heaps

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.