Time complexity to get min elements from max-heap

Question

I was asked in an interview:

What is the best time complexity in getting the min element(s) from a max-heap?

I replied as O(1) assuming the heap size is known and the heap is implemented as a binary heap using an array. This way as per my assumption, the min value is at heap_array[heap_size].

My question is that if this answer is correct. If not, what is the correct answer?

Answer 1

My question is that if this answer is correct.

No, that's not correct. The only guarantee you have, is that each node contains the maximum element of the subtree below it. In other words, the minimum element can be any leaf in the tree.

If not what is the correct answer?

The correct answer is O(n). In each step you need traverse both left and right sub-trees in order to search for the minimum element. In effect, this means that you need to traverse all elements to find the minimum.

Answer 2

Best complexity is O(n). Sketch proof:

• The minimum element could be absolutely any of the lowest-level nodes (in fact it could even not be at the lowest level, but let's start with these).
• There could be up to n/2 lowest-level nodes.
• All of them need to be examined, because the one you're looking for might be in the last place you look. Examining all-but-1 of them doesn't tell you whether the last one is the minimum or not.
• Hence Omega(n) examinations required.

The bound is tight, since clearly we can do it in O(n) by ignoring the fact that our array happens to be a heap.

Moral: it's probably called a heap because (as with the heap of clothes on your bedroom floor) it's easy to get at the top and difficult to get at the rest.