Heap insert, delete k elements

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开发者_如何学C 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!

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

I think I found the solution. At each step, instead of executing extract-min I execute increase-key. I searched for a data structure that has O(1) worst-case time for increase-key, insert-key and get-min, and I found the Brodal queue.

For more information you may look at the Fibonacci heap, because the Brodal queue is based on concepts developed by the Fibonacci heap.

So, at each step I have the following sequence of operations:

1. min = get-min(Auxiliary Heap)

2. let (v1, v2) be the children of min

3. increase-min(Auxiliary Heap, root, v1)

4. insert(Auxiliary heap, v2)

Each of these 4 operations have O(1) worst-case complexity.