How We can Avoid Using Extra work in Heap Sort Algorithm to find Second Largest Element in an array?

Question

Please also let me know the time complexity we can improve.

Answer 1

Heap sort takes O(n Logn) time for sorting n length heap. To obtain second largest element you should use heapify twice. Second number is what you looking for. it takes 2 * logn (heapify) time. Complexity is O(logn).

Answer 2

If only the second largest values is required, then would a single pass bubble sort be quicker? Along the lines of:

biggest = array[0]

foreach element in array
  if element > biggest
    second_biggest = biggest
    biggest = element
  endif
next

which, if I get this right, is O(n).

But, estergones claims O(logn).

However, every value must be inspected at least once, and that's all that the above does so I can't see how the O(logn) is faster / does less work in this case.

Answer 3

If the largest element is in array[0], isn't the second largest in array[1] or array[2]? Since every node is greater or equal than it's two sons (and by transitivity, greater or equal than all its descendants).