Question

In the union of two binomial heaps H1 and H2, the root list of H1 and H2 is merged into a single linked list which is sorted by_-----------
1. Increasing order of the key value of the root nodes.
2. Decreasing order of the key value of the root nodes.
3. Decreasing order of the degree of the root nodes.
4. Increasing order of the degree of the root nodes​

Answer 1

Answer:

Binomial Heap

The main application of Binary Heap is as implement priority queue. Binomial Heap is an extension of Binary Heap that provides faster union or merge operation together with other operations provided by Binary Heap.

A Binomial Heap is a collection of Binomial Trees

What is a Binomial Tree?

A Binomial Tree of order 0 has 1 node. A Binomial Tree of order k can be constructed by taking two binomial trees of order k-1 and making one as leftmost child or other.

A Binomial Tree of order k has following properties.

a) It has exactly 2k nodes.

b) It has depth as k.

c) There are exactly kCi nodes at depth i for i = 0, 1, . . . , k.

d) The root has degree k and children of root are themselves Binomial Trees with order k-1, k-2,.. 0 from left to right.

k = 0 (Single Node)

o

k = 1 (2 nodes)

[We take two k = 0 order Binomial Trees, and

make one as child of other]

o

/

o

k = 2 (4 nodes)

[We take two k = 1 order Binomial Trees, and

make one as child of other]

o

/ \

o o

/

o

k = 3 (8 nodes)

[We take two k = 2 order Binomial Trees, and

make one as child of other]

o

/ | \

o o o

/ \ |

o o o

\

o

The following diagram is referred from 2nd Edition of CLRS book.

BinomialTree