在最小堆中查找k个最小元素

Question

假设我有一个大小为n的最小堆.我想找到最小的k元素而不改变原始的min-heap.运行时应该是theta(k ^ 2).我可以使用记忆theta(k).

我该怎么做？

Answer 1

这是一个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))

假设堆具有索引,您可以使用任何索引检索值heap[index].包含最小值的根的索引是heap.root.candidates是一个辅助最小堆,最初为空,包含值对和堆索引.最小值result按顺序存储.

循环执行k次.所有操作都是恒定时间,除了candidates.remove_min()和candidates.add(),它们是O(log(k)),所以总时间是O(k*log(k)).