Solution

The correct answer is option 1.

Key Points

• The heap's smallest values will always be present on the last level or second last of the heap in a MAX heap, and the time complexity of reaching the last level of the heap is O(n).
• We must use a linear search to search all of the elements in order to find the smallest element and heap.
• It will take O(n) time to traverse all of the elements using linear search. 

Hence the correct answer is O(n).