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

Question

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

如何实现呢？

- Naftaly

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

- Vaughn Cato

---

为什么是-1？你不能只放一个没有注释的东西。 - user1509885

@estro：我认为使用小根堆来存储候选项甚至更好。我已经添加了一些解释。 - Vaughn Cato