python - 什么是堆队列？

Question

阅读 Guido 对问题 Sorting a million 32-bit integers in 2MB of RAM using Python 臭名昭著的回答, 我发现了模块 heapq .

我还发现我不了解 jack ，也不知道我能用它做什么。

您能向我解释一下(众所周知的 6 岁目标)什么是堆队列算法以及您可以用它做什么吗？

您能否提供一个简单 Python 片段，在其中使用它(与 heapq 模块一起)解决了一个用它可以更好地解决的问题，而不是用其他东西？

Answer 1

heapq 实现 binary heaps ，它们是部分排序的数据结构。特别是，它们具有三个有趣的操作:

• heapify 在 O(n) 时间内将列表就地转换为堆；
• heappush 在 O(lg n) 时间内向堆中添加一个元素；
• heappop 在 O(lg n) 时间内从堆中检索最小 元素。

许多有趣的算法都依赖堆来提高性能。最简单的可能是部分排序:获取列表的 k 个最小(或最大)元素，而不对整个列表进行排序。 heapq.nsmallest (nlargest) 就是这样做的。 implementation of nlargest可以解释为:

def nlargest(n, l):
    # make a heap of the first n elements
    heap = l[:n]
    heapify(heap)

    # loop over the other len(l)-n elements of l
    for i in xrange(n, len(l)):
        # push the current element onto the heap, so its size becomes n+1
        heappush(heap, l[i])
        # pop the smallest element off, so that the heap will contain
        # the largest n elements of l seen so far
        heappop(heap)

    return sorted(heap, reverse=True)

分析:设N为l中的元素个数。 heapify 运行一次，成本为 O(n)；那可以忽略不计。然后，在一个运行 N-n = O(N) 次的循环中，我们执行一个 heappop 和一个 heappush 每次花费 O(lg n)，总运行时间为O(N lg n)。当 N >> n 时，与需要 O(N lg N) 时间的其他明显算法 sorted(l)[:n] 相比，这是一个巨大的胜利。