algorithm - 在最小堆中找到 k 个最小元素

Question

假设我有一个大小为 n 的最小堆。我想在不改变原始最小堆的情况下找到最小的 k 元素。运行时应该是 theta(k^2)。我可以使用内存 theta(k)。

我该怎么做？

Answer 1

这是一个伪代码示例:

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