python - Python：修剪 heapq 堆，使其只有 X 个项目长

Question

获得堆的前 X 个项目的最快方法是什么，仍然是堆？

我认为有比通过弹出堆 X 次来重建堆更好的方法。

Answer 1

@Ben 在所有方面都是正确的，尽管 Python 的heapq堆是最小堆而不是最大堆：

newheap = [heappop(oldheap) for _ in range(X)]  # removes from oldheap

通常是最好的。但是，它可以更快，特别是如果 X 几乎与 一样大len(oldheap)，则改为执行此操作：

newheap = sorted(oldheap)[:X]  # doesn't change oldheap

至少在 CPython 中，sort 方法可以利用 中已经存在的偏序，并且比提取最小元素oldheap更快地完成整个列表的排序（排序可以需要更少的比较，而比较是最昂贵的部分）。这方面的极端情况是何时并且已经恰好按排序顺序。然后排序需要总计比较，而重复弹出需要比较的顺序。heappop()XX == len(oldheap)oldheapX-1X*log(X)

Answer 2

就渐近复杂度而言，这实际上是你能做的最好的。您知道前面的项目是最大元素，而亚军是它的孩子之一。但是根节点的另一个子节点可能只有第 100 个最大的节点，较高的 98 在树的另一半。

当然，一旦你取出你的 X 项，你就不需要重新堆放它们——它们已经被排序，因此它们自己是一个格式良好的二进制堆。