# The time complexity for finding the kth smallest number in a min-heap [duplicate]

Suppose that $k < \sqrt n$, what is the time complexity to find the $k_{th}$ smallest number in a min-heap?

I thought that we can remove the root element for k times and each time we apply heapify? So it should be $O(k \log n)$ but the answer is $O (k \log k)$. What did I do wrong?

• stackoverflow.com/questions/7650917/… – xskxzr Feb 8 '18 at 14:04
• You did not use all the info from the problem statement. – Raphael Feb 8 '18 at 15:05
• Are you allowed to destroy the heap? – Raphael Feb 8 '18 at 15:05
• @Raphael yes, I think the link provided in the other comment answers this. – Ahmad Feb 8 '18 at 15:09
• @xskxzr Linking Stack Overflow is rarely useful since their perspective is usually quite different from ours. – Raphael Feb 8 '18 at 15:09

There is an $$O(k)$$ algorithm [1].

[1] Frederickson, G. N. (1993). An optimal algorithm for selection in a min-heap. Information and Computation, 104(2), 197-214.

Here is an $$O(k\log k)$$ algorithm at this SO answer, slightly improved.

Create toVisit, a collection of nodes that contains the nodes which we will traverse next. This is initially just the root node.
Let counter c = 1.
While c < k:
Remove the smallest node from toVisit
Insert that node's children in the given min-heap to toVisit
Return the smallest node from to toVisit


The toVisit can be implemented in a min-heap or balanced BST/B+ tree or skip list in which the insertion and removal of the smallest node takes $$O(\log m)$$ time, where $$m$$ the number of nodes. Assuming the degree of original min-heap is $$O(1)$$, there were at most $$O(k)$$ elements in toVisit since there have been at most $$k$$ insertions.