Im taking a basic comp 250 class and this is a question I was given. No one has been able to figure this question out. The possible answers are at the bottom.Given a minimum-heap H, give a tight O() bound on the time complexity of a method called find3Min that finds, but does not remove, the three smallest keys in H .
Assume the method creates and returns a list of the three smallest elements. To answer this question you need to think of how such a method might be implemented.
1- O(n log(n))
2- O(log(n))
3- O(3 log(n))
4- O(1)
as of now I'm leaning towards 4
The discussion below assumes a binary min heap. The solution for pairing heap and other non-traditional heap types is much different.
In a min heap, the two smallest items are the root item and the smaller of its children. The third smallest is either a child of the root, or a child of the second smallest. Consider these two heaps:
A A
B C B D
D E F G C G F E
In the first, the third smallest is the larger of the root's two children. In the second heap, the third item is a child of the second smallest item. Regardless of how you arrange the heap, the third item will either be a child of the root, or a child of the second smallest.
So you can find the three items in constant time, regardless of the size of the heap. That makes it O(1).
Pseudo code:
s1 = root // smallest item
s2 = root.left
s3 = root.right
if (s2 > s3)
swap(s2, s3)
// s2 now holds the second smallest item
// next smallest is either s3 (other child of root),
// or the smallest of s2's children
if (s3 > s2.left)
s3 = s2.left
if (s3 > s2.right)
s3 = s2.right
Note
The above discussion assumes that all items in the heap are unique (or that "second smallest" means "less than or equal to smallest"). If the heap can have duplicate items and you want the second smallest unique value, then the complexity is O(n).
