Finding the $k$-smallest elements in a min-heap

Given a min-heap $H$, I am interested in finding the $k$ smallest elements efficiently. The simplest solution would be to call delete-min $k$ times which would give us the solution in $O(k \log n)$ time. This can be improved to $O(k \log k)$ time by maintaining a separate heap $H'$ as follows. Start by inserting the root of $H$ in $H'$. Then when performing a delete-min operation, you add both children of that node in $H'$, and repeat until you have all $k$ elements. Is there a way to do better? I have a feeling that $O(k)$ should be possible, but I can't come up with an algorithm - though certainly you cannot hope to do better than $\Omega(k)$.

Edit: I would just like a hint please.

If you mean the usual binary heap represented in an array, this is answered in "An Optimal Algorithm for Selection in a Min-Heap", by Frederickson. It is pretty complex.

Other priority queues have easier algorithms. For instance, if you use a threaded AVL tree as priority queue, you can just follow right neighbor pointers from the minimum value.

• Thanks! This was a given to me as a bonus question. I won't be answering it anymore, but thank you for the reference! – user340082710 Mar 6 '16 at 4:22
• re: "This was given to me as a bonus question": you shouldn't get outside help on your homework without permission from your instructor. – jbapple Mar 6 '16 at 4:26
• It's fine if I reference my sources. I wouldn't have posted otherwise. – user340082710 Mar 6 '16 at 4:34