<p>代码heapq.py在<a href="https://svn.python.org/projects/python/trunk/Lib/heapq.py" rel="nofollow noreferrer">https://svn.python.org/projects/python/trunk/Lib/heapq.py</a>提供</p>
<p><code>nsmallest</code>使用两种算法之一。如果要返回的项目数超过堆中项目总数的10%,那么它将生成列表的副本,对其进行排序,并返回前k个项目。在</p>
<p>如果k小于n/10,则使用堆选择算法:</p>
<pre><code>Make a copy of the first k items, and sort it
for each remaining item in the original heap
if the item is smaller than the largest item in the new list
replace the largest item with the new item
re-sort the new list
</code></pre>
<p>不管是谁写的这个算法都有点低效。至少在理论上,<a href="https://en.wikipedia.org/wiki/Quickselect" rel="nofollow noreferrer">Quick select</a>,这是一个O(n)算法,应该比排序更快,比选择n/10项的“优化”算法快得多。在</p>
<p>我不是一个Python的人,所以我不能肯定,但是我在其他语言方面的经验表明,对于Python来说,上述情况也应该是正确的。在</p>
<h2>更新</h2>
<p>在<a href="https://github.com/python/cpython/blob/master/Lib/heapq.py#L395" rel="nofollow noreferrer">https://github.com/python/cpython/blob/master/Lib/heapq.py#L395</a>处的实现工作方式有些不同。在</p>
<p>如果k大于或等于列表中的项数,则返回包含所有元素的已排序列表。否则,它将使用标准堆选择算法:</p>
^{pr2}$
<p>remove/add组合成一个名为heap_replace的函数。在</p>
<p>如果键是<code>None</code>,那么这里有一个使用标准比较器的优化,但是它使用相同的基本堆选择算法。在</p>
<p>这个实现比我描述的另一个实现要高效得多,尽管我希望它比一般情况下的Quickselect慢。在</p>