0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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)$." $\endgroup$ – Apass.Jack Aug 5 at 15:23
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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)
$\endgroup$
0
$\begingroup$

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

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – David Richerby Aug 7 at 12:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.