Heap insert, delete k elements

Question

Hello,

I have the following problem (I think it's well known/standard) that I am thinking at:

Verify that listing k smallest elements in a binary min-heap is O(k).

I was thinking at traversing the big min-heap in BFS, maintaining a min-heap instead of a simple queue. Initially, the auxiliary min-heap contains the root of my big min-heap. At each step I extract the minimum and I add all its children (maximum 2). The algorithm stops after k extract-mins on the auxiliary min-heap. The size of the auxiliary min-heap is O(k) (for-each min-key extracted I insert its children, maximum 2).

The problem is that extract-min has O(log k) complexity, thus this algorithm has O(k log k) complexity. And I have to find one in O(k).

Do you have any ideas/papers I can use?

Thanks!

Answer 1

Googling for 'heap selection algorithm', I came across 'Frederickson's heap selection algorithm' which leads to this paper (27 pages...).