Search code examples
arraysheapmax-heap

What is the best algorithm to find the minimum element in max heap?

What is the best algorithm(in terms of time complexity) to find the minimum element in max heap?

Solution

  • The minimum element in a max-heap is guaranteed to be in the last (n/2 + 1) items, where n is the number of items in the heap. So the best way to find it is to do a sequential scan of the last n/2 items. Consider, for example, a heap with 5 items:

        5
  4   1
 3 2

    The smallest item will never have children, so it must be either on the bottom row of the heap, or on the next row up.