Second minimum element in a array

Given an array of n numbers a[1], a[2],..., a[n], find the second minimum number in n + log n comparisons.

Answer:


Initially it seems that this can be done in a single pass,
like finding the min element, but dont be tricked, this is not possible.
For example, if the second min happens first and the min element happens later,
then its not possible, ex: {10, 6, 9, 7, 8, 5}

The answer is in fact is in the question itself,
Build a Min Heap - O(n) time
Remove the Root - O(log(n)) time
Remove the Root again, which happens to be the second min element - O(log(n))

So the total time = n + log(n)


See also:
*Selection Sort technique