nlargest 和 nsmallest ; 堆蟒蛇

Question

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

我读它这里的文档。

文档没有说明它是如何在任何可迭代对象上执行的（nsmalles/nlargest）。

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

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

Answer 1

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

取而代之的是，您n使用第一个n项目创建一个较小的 size -max-heap ，然后pushpop使用序列中的其余项目对其进行重复操作。完成后，从堆中弹出项目并以相反的顺序返回它们。

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

该heapq模块包含该算法的纯 Python 实现，但当您导入它时，您可能会得到用 C 编写的代码的更快版本（您也可以阅读该代码的源代码，但它并不那么友好，除非您知道Python C API）。