Sir, in second pass we need logn -1 comparisons. For that, we need to store all the numbers being compared with max element. Now, initially we don't know the max element. So do we end up storing all the elements with which a particular element is compared with, for all the elements in the list ? We can make a binary tree for that but it will require additional space. Can we do it in any better way?
And about the heap, what will be the worst case number of comparisons when building the heap using bottom up approach ? The comparisons will surely be greater than n according to me.
So for building heap, >n comparisons. After finding first maximum, logn comparisons for heapify and then we can get 2nd element. So total number of comparisons using heap will be > n+logn. Am I correct?