怎么会呢heapq.nsmalles公司

Question

我试图根据字典中最小的k个键来确定获取k（key，value）对的最快运行时。 即。： 为

mynahs = {40:(1,3),5:(5,6),11:(9,2),2:(6,3),300:(4,4),15:(2,8)}

smallestK(mynahs,3)

会返回：

^{pr2}$

我见过几种不同的方法：
1在

mylist = list(mynahs.keys())
mylist.sort
mylist = mylist[:k]
return [(k, mynahs[k]) for k in mylist]

但似乎每个人都认为heapq是最快的

cheap = heapq.nsmallest(3, mynahs)
return [(k, mynahs[k]) for k in cheap]

怎么会呢重锤为什么工作最快？我见过this question和{a2} 我还是不明白。是用木槌堆来的吗？这是怎么回事？我也听说过一种叫做quickselect的算法，这就是它所使用的吗？在

它的运行时间是什么？如果字典在不断地变化/更新，则调用heapq.nsmallest公司每次你需要用最快的方法来做到这一点？在

Answer 1

heapq使用一个堆（_heapify_max）

下面是heapq.nsmallest-https://github.com/python/cpython/blob/master/Lib/heapq.py#L395的实现

另请看：

• http://code.activestate.com/recipes/577573-compare-algorithms-for-heapqsmallest/

Answer 2

代码heapq.py在https://svn.python.org/projects/python/trunk/Lib/heapq.py提供

nsmallest使用两种算法之一。如果要返回的项目数超过堆中项目总数的10%，那么它将生成列表的副本，对其进行排序，并返回前k个项目。在

如果k小于n/10，则使用堆选择算法：

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

不管是谁写的这个算法都有点低效。至少在理论上，Quick select，这是一个O（n）算法，应该比排序更快，比选择n/10项的“优化”算法快得多。在

我不是一个Python的人，所以我不能肯定，但是我在其他语言方面的经验表明，对于Python来说，上述情况也应该是正确的。在

更新

在https://github.com/python/cpython/blob/master/Lib/heapq.py#L395处的实现工作方式有些不同。在

如果k大于或等于列表中的项数，则返回包含所有元素的已排序列表。否则，它将使用标准堆选择算法：

^{pr2}$

remove/add组合成一个名为heap_replace的函数。在

如果键是None，那么这里有一个使用标准比较器的优化，但是它使用相同的基本堆选择算法。在

这个实现比我描述的另一个实现要高效得多，尽管我希望它比一般情况下的Quickselect慢。在