Question

The binomial tree Bk is an ordered tree (see Section B.5.2) defined recursively.
As shown in Figure 19.6(a), the binomial tree B0 consists of a single node. The
binomial tree Bk consists of two binomial trees Bk1 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 B0 through B4.

Suppose that we were to implement only the mergeable-heap operations on a
Fibonacci heap (i.e., we do not implement the DECREASE-KEY or 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 [log n].

Answer 1