Cheap and Secure Web Hosting Provider : See Now

# [Solved]: Determine the smallest $3$ numbers in a set using comparisons

, ,
Problem Detail:

Given a set of $n$ distinct numbers, we would like to determine the smallest $3$ numbers in this set using comparisons. The elements can be determined using $n+O(\log n)$ comparisons.

This was the answer given in a multiple choice question. Now, we can easily do this using $3n\in O(n)$ comparisons. However I have been thinking about it and I can't do it in $n+O(\log n)$ comparisons.

They might be thinking about making a heap and using heapify which takes $O(n)$ time. However in heapify, the comparisons are $O(n)$ but not like $n+O\log(n)$ because every step in the heapify needs finding the minimum among $3$ numbers which takes $3$ comparisons so making a heap and finding the three minimums should be $3n$ comparisons.

So, can anyone tell me how to find three minimums in $n+O(\log n)$ comparisons or am I messing up somewhere in the heapify logic?

###### Asked By : Arghya Chakraborty

I can show you how to get the two smallest elements in $n + O( \log n)$ comparisons, the extension to the three smallest elements should not be difficult.

Build the following tree. Start with your array, then for each pair of neighboring elements (non-overlapping), promote the smaller one level up. Do the same for the new level, until the tree has a root.

This tree is built using less than $n$ comparisons ($n / 2 + n / 4 + \dots$). The smallest element is obviously the root. The second smallest element must be one of of the siblings of all the nodes that are equal to the root along the path down the tree to the array level. There are at most $\log n$ such nodes.

You should also convince yourself of the bound when the number of nodes on a level is not even.