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.

StackExchange Computer Science Q#54066, answer score: 4