从Python heapq中获取最小值

Question

来自Python文档的内容：

后面提到的这两个函数 [heapq.nlargest 和 heapq.nsmallest] 在处理较小的n值时表现最好。对于较大的n值，使用 sorted() 函数会更高效。而且，当 n==1 时，使用内置的 min() 和 max() 函数会更有效率。

如果我想从最小堆中获取最小的元素，为什么Python文档建议使用 min() 函数呢？我认为这个函数的运行时间是 O(n)，而我可以直接在堆中以 O(1) 的时间获取第一个元素？（我假设堆中的第一个元素就是最小值）

Answer 1

如果你只需要从一个已经整理好的列表中找出最小的元素，可以直接用 list[0] 来获取：

import heapq
lst = [1,-1,100,200]
heapq.heapify(lst)

min_value = lst[0]

上面的文档提到的是获取 n 个最小的数字，但如果 n 很大的话，堆这种数据结构并不是最有效的选择。

Answer 2

nsmallest 和 nlargest 这两个方法来自于 heapq，它们并不假设传入的参数已经是堆的格式。相反，它们在遍历参数时会尝试“堆化”这个参数。这种方法在寻找前 k 个元素时，对于小的 k 值来说，比直接排序要高效得多。不过，如果 k 恰好等于 1，直接使用 min 会更快，因为这样可以避免在遍历时进行堆化的额外开销。

你的说法是对的。如果你有一个数组，并且可以保证它已经被堆化且没有被修改，那么访问第一个元素就能得到最小值（对于最大堆来说则是最大值）。

看一下 heapq 的源代码（也许我在看旧代码？），我觉得这看起来还是挺奇怪的。nsmallest 对于 n == 1 有一个特殊的处理方式，如下所示（第 397 行）：

def nsmallest(n, iterable, key=None):
    """Find the n smallest elements in a dataset.

    Equivalent to:  sorted(iterable, key=key)[:n]
    """
    # Short-cut for n==1 is to use min() when len(iterable)>0
    if n == 1:
        it = iter(iterable)
        head = list(islice(it, 1))
        if not head:
            return []
        if key is None:
            return [min(chain(head, it))]
        return [min(chain(head, it), key=key)] 

    # ... rest of function

在解释器中玩这个表达式会让人觉得很奇怪：

In [203]: foo = list(itertools.islice([1,2,3], 1)); it = iter([1,2,3]); x = itertools.chain(foo, it);

In [204]: x.next()
Out[204]: 1

In [205]: x.next()
Out[205]: 1

In [206]: x.next()
Out[206]: 2

In [207]: x.next()
Out[207]: 3

In [208]: x.next()
---------------------------------------------------------------------------
StopIteration                             Traceback (most recent call last)
<ipython-input-208-e05f366da090> in <module>()
----> 1 x.next()

StopIteration:

它似乎在构建一个生成器（这个生成器会立即变成一个 list），只取第一个元素（这在最小堆中是可以预期的），但接着又奇怪地将它和一个普通的生成器连接在一起，这个生成器会遍历整个数组。

我同意，如果你从一个 list 开始并想查询最小元素，最好还是保持它为 list 并使用 min。不过，如果你手里有一个最小堆，确实应该直接查看第一个元素——这正是堆化的目的所在。

但无论如何，这段源代码在将最小堆传给 min 时看起来相当奇怪——我非常希望能有更多的解释来说明它在做什么——如果有更近期的 C 级代码实现 heapq 的话，也希望能指引我一下。