Time complexity to get min elements from max-heap
algorithm, heap
Solution
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.
Problem
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?