19-2 Binomial trees and binomial heaps

The binomial tree $B_k$ is an ordered tree (see Section B.5.2) defined recursively. As shown in Figure 19.6(a), the binomial tree $B_0$ consists of a single node. The binomial tree $B_k$ consists of two binomial trees $B_{k - 1}$ that are linked together so that the root of one is the leftmost child of the root of the other. Figure 19.6(b) shows the binomial trees $B_0$ through $B_4$.

a. Show that for the binomial tree $B_k$,

1. there are $2^k$ nodes,
2. the height of the tree is $k$,
3. there are exactly $\binom{k}{i}$ nodes at depth $i$ for $i = 0, 1, \ldots, k$, and
4. the root has degree $k$, which is greater than that of any other node; moreover, as Figure 19.6(c) shows, if we number the children of the root from left to right by $k - 1, k - 2, \ldots, 0$, then child $i$ is the root of a subtree $B_i$.

A binomial heap $H$ is a set of binomial trees that satisfies the following properties:

1. Each node has a $key$ (like a Fibonacci heap).
2. Each binomial tree in $H$ obeys the min-heap property.
3. For any nonnegative integer $k$, there is at most one binomial tree in $H$ whose root has degree $k$.

b. Suppose that a binomial heap $H$ has a total of $n$ nodes. Discuss the relationship between the binomial trees that $H$ contains and the binary representation of $n$. Conclude that $H$ consists of at most $\lfloor \lg n \rfloor + 1$ binomial trees.

Suppose that we represent a binomial heap as follows. The left-child, right-sibling scheme of Section 10.4 represents each binomial tree within a binomial heap. Each node contains its key; pointers to its parent, to its leftmost child, and to the sibling immediately to its right (these pointers are $\text{NIL}$ when appropriate); and its degree (as in Fibonacci heaps, how many children it has). The roots form a singly linked root list, ordered by the degrees of the roots (from low to high), and we access the binomial heap by a pointer to the first node on the root list.

c. Complete the description of how to represent a binomial heap (i.e., name the attributes, describe when attributes have the value $\text{NIL}$, and define how the root list is organized), and show how to implement the same seven operations on binomial heaps as this chapter implemented on Fibonacci heaps. Each operation should run in $O(\lg n)$ worst-case time, where $n$ is the number of nodes in the binomial heap (or in the case of the $\text{UNION}$ operation, in the two binomial heaps that are being united). The $\text{MAKE-HEAP}$ operation should take constant time.

d. Suppose that we were to implement only the mergeable-heap operations on a Fibonacci heap (i.e., we do not implement the $\text{DECREASE-KEY}$ or $\text{DELETE}$ operations). How would the trees in a Fibonacci heap resemble those in a binomial heap? How would they differ? Show that the maximum degree in an $n$-node Fibonacci heap would be at most $\lfloor \lg n\rfloor$.

e. Professor McGee has devised a new data structure based on Fibonacci heaps. A McGee heap has the same structure as a Fibonacci heap and supports just the mergeable-heap operations. The implementations of the operations are the same as for Fibonacci heaps, except that insertion and union consolidate the root list as their last step. What are the worst-case running times of operations on McGee heaps?

a.

1. $B_k$ consists of two binomial trees $B_{k - 1}$.
2. The height of one $B_{k - 1}$ is increased by $1$.
3. For $i = 0$, $\binom{k}{0} = 1$ and only root is at depth $0$. Suppose in $B_{k - 1}$, the number of nodes at depth $i$ is $\binom{k - 1}{i}$, in $B_k$, the number of nodes at depth $i$ is $\binom{k - 1}{i} + \binom{k - 1}{i - 1} = \binom{k}{i}$.
4. The degree of the root increase by $1$.

b. Let $n.b$ denote the binary expansion of $n$. The fact that we can have at most one of each binomial tree corresponds to the fact that we can have at most $1$ as any digit of $n.b$. Since each binomial tree has a size which is a power of $2$, the binomial trees required to represent n nodes are uniquely determined. We include $B_k$ if and only if the $k$th position of $n.b$ is $1$. Since the binary representation of $n$ has at most $\lfloor \lg n \rfloor+ 1$ digits, this also bounds the number of trees which can be used to represent $n$ nodes.

c. Given a node $x$, let $x.key$, $x.p$, $x.c$, and $x.s$ represent the attributes key, parent, left-most child, and sibling to the right, respectively. The pointer attributes have value $\text{NIL}$ when no such node exists. The root list will be stored in a singly linked list.

• MAKE-HEAP initialize an empty list for the root list and return a pointer to the head of the list, which contains $\text{NIL}$. This takes constant time. To insert: Let $x$ be a node with key $k$, to be inserted. Scan the root list to find the first $m$ such that $B_m$ is not one of the trees in the binomial heap. If there is no $B_0$, simply create a single root node $x$. Otherwise, union $x, B_0, B_1, \ldots, B_{m - 1}$ into a $B_m$ tree. Remove all root nodes of the unioned trees from the root list, and update it with the new root. Since each join operation is logarithmic in the height of the tree, the total time is $O(\lg n)$. $\text{MINIMUM}$ just scans the root list and returns the minimum in $O(\lg n)$, since the root list has size at most $O(\lg n)$.
• EXTRACT-MIN: finds and deletes the minimum, then splits the tree Bm which contained the minimum into its component binomial trees $B_0, B_1, \ldots, B_{m - 1}$ in $O(\lg n)$ time. Finally, it unions each of these with any existing trees of the same size in $O(\lg n)$ time.
• UNION: suppose we have two binomial heaps consisting of trees $B_{i_1}, B_{i_2}, \ldots, B_{i_k}$ and $B_{j_1}, B_{j_2}, \ldots, B_{j_m}$ respectively. Simply union orresponding trees of the same size between the two heaps, then do another check and join any newly created trees which have caused additional duplicates. Note: we will perform at most one union on any fixed size of binomial tree so the total running time is still logarithmic in $n$, where we assume that $n$ is sum of the sizes of the trees which we are unioning.
• DECREASE-KEY: simply swap the node whose key was decreased up the tree until it satisfies the min-heap property. This method requires that we swap the node with its parent along with all their satellite data in a brute-force manner to avoid updating $p$ attributes of the siblings of the node. When the data stored in each node is large, we may want to update $p$ instead, which, however, will increase the running time bound to $O(\lg^2 n)$.
• DELETE: note that every binomial tree consists of two copies of a smaller binomial tree, so we can write the procedure recursively. If the tree is a single node, simply delete it. If we wish to delete from $B_k$, first split the tree into its constituent copies of $B_{k - 1}$, and recursively call delete on the copy of $B_{k - 1}$ which contains $x$. If this results in two binomial trees of the same size, simply union them.

d. The Fibonacci heap will look like a binomial heap, except that multiple copies of a given binomial tree will be allowed. Since the only trees which will appear are binomial trees and $B_k$ has $2k$ nodes, we must have $2k \le n$, which implies $k \le \lfloor \lg n \rfloor$. Since the largest root of any binomial tree occurs at the root, and on $B_k$ it is degree $k$, this also bounds the largest degree of a node.

e. $\text{INSERT}$ and $\text{UNION}$ will no longer have amortized $O(1)$ running time because $\text{CONSOLIDATE}$ has runtime $O(\lg n)$. Even if no nodes are consolidated, the runtime is dominated by the check that all degrees are distinct.

Since calling $\text{UNION}$ on a heap and a single node is the same as insertion, it must also have runtime $O(\lg n)$. The other operations remain unchanged.