python-2.7 - nlargest 和 nsmallest ;堆 python

Question

这是出于对 python 中 heapq.py 模块的 nsmallest 和 nlargest 方法的好奇。

我在读它here在文档中。

文档没有说明它是如何在任何可迭代对象上这样做的(nsmalles/nlargest)。

这可能是一个愚蠢的问题，但我可以假设这些方法在内部创建一个可迭代数据结构的堆(可能使用“heapify”方法)，然后返回 n 个最小/最大元素吗？

只是想证实我的结论。谢谢!

Answer 1

查找 n 的算法N 的可迭代项中的最小或最大项项目有点棘手。你看，你没有创建大小- N min-heap 找到最小的项目。

取而代之的是，您制作了一个更小的尺寸- n第一个 n 的最大堆项目，然后重复 pushpop使用序列中的剩余项目对其进行操作。完成后，从堆中弹出项目并以相反的顺序返回它们。

这个过程需要O(N log(n))时间(注意小的 n )当然只有 O(n)空间。如果 n远小于 N ，它比排序和切片效率高得多。

heapq module包含该算法的纯 Python 实现，但是当您导入它时，您可能会得到用 C 编写的代码的更快版本(您也可以阅读 the source for that，但除非您了解 Python C，否则它不太友好API)。