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?