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?

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

| cite | improve this answer | |

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.


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