最大和最小; heapq python

Question

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

我正在阅读文档here。

该文档没有说明它如何在任何迭代器上这样做（nsmalles/nlargest）。

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

只是想确认我的结论。谢谢！

Answer 1

用于从N项目中查找可迭代的最小或最大项目的算法有点棘手。你看，你不会创建一个大小 - N分钟堆找到最小的项目。

相反，你犯了一个小的，大小 - n最大堆与第一n项目，然后反复做就可以了pushpop操作从序列剩余项目。一旦你完成了，你从堆中弹出这些项并按相反的顺序返回它们。

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

的heapq module包含纯Python实现这个算法，虽然当你导入它，你可能会用C语言编写的代码的速度更快的版本，而不是（你可以阅读the source for that太多，但它并不完全，除非你作为友好知道Python C API）。