# Time Complexity To find Kth smallest element in a min heap

In a min heap of n elements, the Kth smallest element can be found in?

O(n)
O(nlogn)
O(logn)
O(1).

According to me ans should be O(n), say we can have a case where k=n, then we can only find the smallest element in the leaf nodes, which will contain n/2 elements and we need to search O(n/2), i.e. O(n). Is my approach correct?

• The question sounds ambiguous. If $K$-th element can be found in $O(n)$, then it can also be found in $O(n\log n)$. Here is a better version, "which one of the following is the tightest bound among them for an algorithm that finds the $K$-th smallest element in a min heap, $O(n)$, $O(n\log n)$, $O(\log n)$ and $O(1)$". Or "Describe an algorithm that finds the $K$-th smallest element in a min heap in $O(k\log k)$." – Apass.Jack Aug 5 at 15:23

None of the answers is correct. It is $$O(\min(k \log n, n))$$.

If $$k < n/\log n$$ then doing $$k$$ pops and checking the minimal element is fastest, otherwise a scan through the whole heap is faster.

It can be done in O(klogk) time when k is the kth smallest element

lets say we have an arbitrary min heap - H1 with n elements
in order to find the kth smallest element in this heap, we need an additional heap - H2
-we assume that every element in H2 points at the matching element in H1 so we have O(1) access to the element's children(2.1)

### the algorithm:

1. create a new min heap - H2 initialize H2 to contain the root node of H1
2. do k-1 times:
1. 1 let x be the root element of H2, remove x from H2 and insert into H2 the children of x in H1(the direct children a node has at most 2 children)
3. return the element that is in top of H2
the loop takes O(k) time, each insertion to H2 is O(logk) in the worst case. so its O(klogk)

There's a O(K) Algorithm mentioned in the below link.

https://www.sciencedirect.com/science/article/pii/S0890540183710308

• Welcome to the site! Please give a full citation to this paper (authors, title, etc) and also a brief summary of the answer. At the moment, your answer is in danger of becoming completely useless the next time Science Direct reorganize their website. – David Richerby Aug 7 at 12:00