这是出于对 python 中 heapq.py 模块的 nsmallest 和 nlargest 方法的好奇。
我正在读它here https://docs.python.org/2/library/heapq.html#在文档中。
文档没有说明它如何在任何可迭代上执行此操作（nsmalles/nlargest）。
这可能是一个愚蠢的问题，但是我可以假设这些方法在内部创建一个可迭代数据结构的堆（可能使用“heapify”方法），然后返回 n 个最小/最大元素吗？
只是想证实我的结论。谢谢！
寻找的算法n可迭代的最小或最大项目N项目有点棘手。你看，你没有创建一个尺寸-Nmin-heap 查找最小的项目。
相反，你会制作一个更小的尺寸-n最大堆与第一个n项目，然后重复pushpop使用序列中的剩余项目对其进行操作。完成后，您可以从堆中弹出项目并以相反的顺序返回它们。
这个过程需要O(N log(n))时间（注意小n）当然只有O(n)空间。如果n远小于N，比排序和切片效率高很多。
The heapq module https://hg.python.org/cpython/file/default/Lib/heapq.py包含该算法的纯 Python 实现，尽管当您导入它时，您可能会获得用 C 编写的代码的更快版本（您可以阅读的来源 https://hg.python.org/cpython/file/default/Modules/_heapqmodule.c也是如此，但除非您了解 Python C API，否则它不太友好）。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
