Search for k smallest items in the minimum heap

Question

Suppose I have a minimal heap of size n. I want to find the smallest k elements without changing the original mini-heap. Runtime must be theta (k ^ 2). I can use theta (k) memory.

How can i do this?

Answer 1

Here is an example pseducode:

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

The heap is supposed to have indices, and you can get the value at any index using heap[index] . The root index containing the minimum value is heap.root . candidates is a secondary minimum 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 candidates.remove_min() and candidates.add() , which are O (log (k)), so the total time is O (k * log (k)).