The binomial tree B k is an ordered tree (see Section B.5.2) defined recursively. As shown in

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 Bk-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 B0 through B4.

a. Show that for the binomial tree Bk,

1. There are 2k nodes,

2. The height of the tree is k,

3. There are exactly (kI) 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, as Figure 19.6(c) shows, if we number the children of the root from left to right by k − 1, k − 2, . . . ,0, then child i is the root of a subtree Bi .

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 ⌊lg n⌋ + 1 binomial trees.

image

Figure 19.6 

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

Suppose that we represent a binomial heap as follows. The left-child, rightsibling 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 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 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 UNION operation, in the two binomial heaps that are being united). The 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 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 ⌊lg n⌋.

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?

Fantastic news! We've Found the answer you've been seeking!

Step by Step Answer:

Related Book For  book-img-for-question

Introduction to Algorithms

ISBN: 978-0262033848

3rd edition

Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest

Question Posted: