Kth Largest element in Min-Heap

Question

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?

Comments

I think its O(n) because you have to go through the N/2 to N part of the heap.

---

Yeah, the nth largest element will be present in one of the leaf nodes, which will take $O(n)$

---

Yes, It will be O(n).

---

https://www.geeksforgeeks.org/maximum-element-in-min-heap/

Answer 1

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.

Comments

Suppose the min heap has elements 1,2,3,4,5 ,6 in that order . And we want to find 4th largest element.
How can you say the 4th largest element will be present in the leaves.?

---

I am not saying that all elements are present in the leaves. Obviously some elements will not be leaves and will be Kth largest element in heap. If element is not in the leaves we won't need O(n) time. We will need less than that.

But if the element is present in the leaf nodes we will need O(n/2) time and hence time complexity is O(n).