Finding k smallest elements in a minimum heap

Question

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?

Answer 1

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)).