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?
Correct answer is O(n) 1) to find minimum element from max heap Find nth max(which is nothing but minimum element) Which will take n(n-1)/2 comparisons == O(n^2) 2) first at all it is array To find minimum element apply selection sort 1st pass Which will take O(n) time. 3) delete one by one (upto) n elements in max heap(it is nothing but finding only) Which will take O(nlogn) time. Among 3 ways the best one is O(n). So correct answer will be O(n) time
Best complexity is O(n).
Rather than, not wrote here a lot about that,
The min element in MAX-heap, and the MAX element in min-heap
Can be also at the (lowest level - 1) and not always in lowest level.
explain:
because in heap there is an option of missing nodes from the right side of the lowest level, it could be not a balancing (fully) tree, what makes it to have leafs also in (lower level -1).
what means that there are n/2 to check. so in big O term it's equal to O(n).
Examples for situation like that:
