3,248 views
2 votes
2 votes
I was going through the heap concept and one question came into my mind what will be the best case time complexity of finding the minimum element in a max heap?

Thank you:)

1 Answer

Best answer
2 votes
2 votes
Minimum element in a Max heap will always be one of the leaf nodes of the heap.

Leaf nodes in heaps range from $\left \lfloor \frac{n}{2} \right \rfloor+1$  to $n$.

so in the best case we need to check $\frac{n}{2}$ elements.

$\therefore$ time complexity is $\Omega (n)$ for finding minimum element in a max-heap in best case.

OR

Assume that heap is stored in array and then we apply linear search on the second half of the array since all the leaf nodes will be in second half of the array

So T.C. = $\Omega (\frac{n}{2}) = \Omega(n)$
edited by

Related questions

11 votes
11 votes
5 answers
1
Vikrant Singh asked Dec 28, 2014
3,611 views
What is the complexity of finding $50^{th}$ smallest element in an already constructed binary min-heap?$\Theta(1)$$\Theta (\log n)$$\Theta (n)$$\Theta (n \log n)$
1 votes
1 votes
1 answer
2
8 votes
8 votes
3 answers
3
Kapil asked Sep 4, 2016
3,885 views
In a min-heap with n elements1). The 7th smallest element can be found in time, if duplicates are allowed ?2). The 7th distinct smallest element can be found in time, I...
1 votes
1 votes
1 answer
4
gmrishikumar asked Dec 1, 2018
2,248 views
What is the time complexity to find the Kth largest element in a Min-Heap? Or equivalently, What is the time complexity to find Kth smallest element in Max-Heap?