recategorized by
2,253 views
1 votes
1 votes
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?
recategorized by

1 Answer

Best answer
2 votes
2 votes
The nth largest element will be present in one of the leaf nodes, and will take O(n/2) time to find.

Therefore O(n) is the required complexity.

Related questions

8 votes
8 votes
3 answers
1
Kapil asked Sep 4, 2016
3,892 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...
11 votes
11 votes
5 answers
2
Vikrant Singh asked Dec 28, 2014
3,618 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
3