(JAVA)Almost a priority queue. Design a data structure that supports the following operations for almost a priority queue: (i) FindSecondSmallest() which returns the second smallest item in the data structure. (ii) Insert(x) which inserts item x to the data structure. (iii) DeleteSecondSmallest() which removes the second smallest item from the data structure. Your data structure should implement the operation FindSecondSmallest() in O(1), and the other two operations in O(log n), where n is the number of elements in the data structure. 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).
(JAVA)Almost a priority queue. Design a data structure that supports the following
operations for almost a priority queue:
(i) FindSecondSmallest() which returns the second smallest item in the data structure.
(ii) Insert(x) which inserts item x to the data structure.
(iii) DeleteSecondSmallest() which removes the second smallest item from the data
structure.
Your data structure should implement the operation FindSecondSmallest() in O(1), and
the other two operations in O(log n), where n is the number of elements in the data
structure.
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).
Step by step
Solved in 4 steps with 3 images
