Finding k smallest elements in a minimum heap

algorithm

Solution

Here is a pseducode example:

candidates.add((heap[heap.root],heap.root))
while len(result)<k:
  (min_value,i)=candidates.remove_min()
  result.append(min_value)
  l=heap.left_child(i)
  r=help.right_child(i)
  candidates.add((heap[l],l))
  candidates.add((heap[r],r))

It is assumed that the heap has indices, and you can retrieve the value at any index using `heap[index]`. The index of the root, containing the minimum value, is `heap.root`. `candidates` is a secondary min heap, initially empty, containing pairs of values and heap indices. The minimum values are stored in `result`, in order.

The loop executes k times. All operations are constant time except for `candidates.remove_min()` and `candidates.add()`, which are O(log(k)), so the total time is O(k*log(k)).

Problem

Suppose I have a minimum heap of size n. I want to find smallest k elements without changing the original min-heap. Run-time should be theta(k^2). I can use memory theta(k). How can I do it?

Original source