A min-heap is useful when we are interested in the minimum value of a set of numbers. Now, instead of the min, we are interested in the K-th smallest value. a.) ) Please design a data structure to allow the following two operations: push (insert a new number) and find_Kmin (return the value of the K-th smallest number without removing it). Both operations should be done in O(log K) time. b.) In addition to push and find_Kmin, now we also want to support the pop operation to return and remove the K-th smallest element. Please design a data structure to support these three operations, and each operation should take O(log n) time with n being the size of the current set.
A min-heap is useful when we are interested in the minimum value of a
set of numbers. Now, instead of the min, we are interested in the K-th smallest value.
a.) ) Please design a data structure to allow the following two operations: push (insert a new
number) and find_Kmin (return the value of the K-th smallest number without removing it). Both
operations should be done in O(log K) time.
b.) In addition to push and find_Kmin, now we also want to support the pop operation to
return and remove the K-th smallest element. Please design a data structure to support these three
operations, and each operation should take O(log n) time with n being the size of the current set.
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
For part a how is this right? Say we have a case of these 4 numbers pushed sequentially, 1, 7, 9, and 11. The k-last behavior will not be correct.
by Bartleby Expert
