19.1 Binomial trees and binomial heaps

| < Day Day Up > |

## 19.1 Binomial trees and binomial heaps

A binomial heap is a collection of binomial trees, so this section starts by defining binomial trees and proving some key properties. We then define binomial heaps and show how they can be represented.

### 19.1.1 Binomial trees

The binomial tree Bk is an ordered tree (see Section B.5.2) defined recursively. As shown in Figure 19.2(a), the binomial tree B0 consists of a single node. The binomial tree Bk consists of two binomial trees Bk-1 that are linked together: the root of one is the leftmost child of the root of the other. Figure 19.2(b) shows the binomial trees B0 through B4.

Figure 19.2: (a) The recursive definition of the binomial tree Bk. Triangles represent rooted subtrees. (b) The binomial trees B0 through B4. Node depths in B4 are shown. (c) Another way of looking at the binomial tree Bk.

Some properties of binomial trees are given by the following lemma.

Lemma 19.1: (Properties of binomial trees)

For the binomial tree Bk,

1. there are 2k nodes,

2. the height of the tree is k,

3. there are exactly nodes at depth i for i = 0, 1, ..., k, and

4. the root has degree k, which is greater than that of any other node; moreover if i the children of the root are numbered from left to right by k - 1, k - 2, ..., 0, child i is the root of a subtree Bi.

Proof The proof is by induction on k. For each property, the basis is the binomial tree B0. Verifying that each property holds for B0 is trivial.

For the inductive step, we assume that the lemma holds for Bk-1.

1. Binomial tree Bk consists of two copies of Bk-1, and so Bk has 2k-1 + 2k-1 = 2k nodes.

2. Because of the way in which the two copies of Bk-1 are linked to form Bk, the maximum depth of a node in Bk is one greater than the maximum depth in Bk-1. By the inductive hypothesis, this maximum depth is (k - 1) + 1 = k.

3. Let D(k, i) be the number of nodes at depth i of binomial tree Bk. Since Bk is composed of two copies of Bk-1 linked together, a node at depth i in Bk-1 appears in Bk once at depth i and once at depth i + 1. In other words, the number of nodes at depth i in Bk is the number of nodes at depth i in Bk-1 plus the number of nodes at depth i - 1 in Bk-1. Thus,

4. The only node with greater degree in Bk than in Bk-1 is the root, which has one more child than in Bk-1. Since the root of Bk-1 has degree k - 1, the root of Bk has degree k. Now, by the inductive hypothesis, and as Figure 19.2(c) shows, from left to right, the children of the root of Bk-1 are roots of Bk-2, Bk-3, ..., B0. When Bk-1 is linked to Bk-1, therefore, the children of the resulting root are roots of Bk-1, Bk-2, ..., B0.

Corollary 19.2

The maximum degree of any node in an n-node binomial tree is lg n.

Proof Immediate from properties 1 and 4 of Lemma 19.1.

The term "binomial tree" comes from property 3 of Lemma 19.1, since the terms are the binomial coefficients. Exercise 19.1-3 gives further justification for the term.

### 19.1.2 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 〈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.

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.

Exercises 19.1-1

Suppose that x is a node in a binomial tree within a binomial heap, and assume that sibling[x] ≠ NIL. If x is not a root, how does degree[sibling[x]] compare to degree[x]? How about if x is a root?

Exercises 19.1-2

If x is a nonroot node in a binomial tree within a binomial heap, how does degree[x] compare to degree[p[x]]?

Exercises 19.1-3

Suppose we label the nodes of binomial tree Bk in binary by a postorder walk, as in Figure 19.4. Consider a node x labeled l at depth i, and let j = k - i. Show that x has j 1's in its binary representation. How many binary k-strings are there that contain exactly j 1's? Show that the degree of x is equal to the number of 1's to the right of the rightmost 0 in the binary representation of l.

Figure 19.4: The binomial tree B4 with nodes labeled in binary by a postorder walk.

| < Day Day Up > |