6
$\begingroup$

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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ The tree that you built is a heap right? Then the third highest will be one of the siblings of the smallest element nodes or the second smallest element nodes. Did I get it right? $\endgroup$
    – User Not Found
    Dec 2, 2016 at 2:04
  • $\begingroup$ @ArghyaChakraborty It isn't a heap. Consider it as a knock out tournament based on which element is smaller. At each step half of the elements get knocked out. The other two elements can be found by considering the fact that the second smallest must have lost the tournament from the smallest number at some point. which is pointed as a sibling to the smallest number in the answer. Similarly you can find the third smallest. It has to be the sibling of second smallest. $\endgroup$
    – Shubham Singh rawat
    Dec 2, 2016 at 5:22
  • $\begingroup$ @ShubhamSinghrawat It is what we call a winner tree. They do have the heap property if I am not mistaken. $\endgroup$
    – User Not Found
    Dec 2, 2016 at 7:49
  • $\begingroup$ @arghya Chakraborty heaps are usually used to implement dictionaries which doesn't use duplicate elements. However this tree does although they might satisfy min heap property $\endgroup$
    – Shubham Singh rawat
    Dec 2, 2016 at 7:57
  • $\begingroup$ @ShubhamSinghrawat Ok that is something new for me...Thanks $\endgroup$
    – User Not Found
    Dec 2, 2016 at 8:30
-1
$\begingroup$

I'd suggest to look at the following classical algorithm of finding the k-th smallest element in linear time.

https://en.m.wikipedia.org/wiki/Median_of_medians

Improve this answer
$\endgroup$
2
  • $\begingroup$ the kth smallest element algorithm is going to return a single element/ Running the same for three times is going to be a costly affair, isn't it? $\endgroup$
    – Shubham Singh rawat
    Dec 2, 2016 at 2:08
  • 2
    $\begingroup$ I think the algorithm you suggest will use more than $n+O(\log n)$ comparisons. Its running time (and number of comparisons) is $O(n)$, but that's different and might be larger than $n+O(\log n)$ (and probably is, for that particular algorithm). Linear time isn't enough. So, this doesn't answer the question that was asked. $\endgroup$
    – D.W. ♦
    Dec 2, 2016 at 2:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.