Problem 4: Binomial heaps. Let H1 and H2 be two binomial heaps. We would like to merge H1 and H2 to obtain the binomial heap H and also to find the minimum key in H. A standard approach would be to perform the following sequence of operations H = Merge(H1, H2); m = Min(H). Alternatively, we may perform the following sequence of operations m1 = Min(H1); m2 = Min(H2); m = min{m1, m2}; H = Merge(H1, H2). (i) Give an example of heaps H1 and H2 in which the time complexity of all operations together in the standard approach is better than in the alternative approach. Note that the time complexity of finding the minimum element in the binomial heap depends on the number of binomial trees in the heap. Justify your answer. (ii) Does there exist an example of heaps H1 and H2 in which the time complexity of all operations together in the alternative approach is better than in the standard approach. Again note that the time complexity of finding the minimum element in the binomial heap depends on the number of binomial trees in the heap. Justify your answer.
Problem 4: Binomial heaps. Let H1 and H2 be two binomial heaps. We would like to
merge H1 and H2 to obtain the binomial heap H and also to find the minimum key in H.
A standard approach would be to perform the following sequence of operations
H = Merge(H1, H2);
m = Min(H).
Alternatively, we may perform the following sequence of operations
m1 = Min(H1);
m2 = Min(H2);
m = min{m1, m2};
H = Merge(H1, H2).
(i) Give an example of heaps H1 and H2 in which the time complexity of all operations together in the standard approach is better than in the alternative approach.
Note that the time complexity of finding the minimum element in the binomial heap
depends on the number of binomial trees in the heap. Justify your answer.
(ii) Does there exist an example of heaps H1 and H2 in which the time complexity of
all operations together in the alternative approach is better than in the standard
approach. Again note that the time complexity of finding the minimum element in
the binomial heap depends on the number of binomial trees in the heap. Justify your
answer.
Step by step
Solved in 3 steps
