heapq

heapq — Heap queue algorithm

2.3版本的新功能。

源代码： Lib / heapq.py

该模块提供了堆队列算法的实现，也称为优先级队列算法。

堆是二叉树，每个父节点的值小于或等于其任何子节点。该实现使用数组heap[k] <= heap[2*k+1]，heap[k] <= heap[2*k+2]对于所有的k，从零开始计数元素。为了比较，不存在的元素被认为是无限的。堆的有趣属性是它的最小元素始终是根，heap[0]。

下面的API与教科书堆算法在两个方面不同：（a）我们使用从零开始的索引。这使得节点的索引与其子节点的索引之间的关系略微不明显，但是由于Python使用了从零开始的索引，因此更合适。（b）我们的弹出方法返回最小的项目，而不是最大的项目（在教科书中称为“最小堆”;由于其适用于原地排序，因此“最大堆”在文本中更常见）。

这两个可以将堆看作一个常规的Python列表而不出意外：heap[0]是最小的项目，并且heap.sort()保持堆不变！

要创建堆，请使用初始化为的列表[]，或者您可以通过函数将填充列表转换为堆heapify()。

提供以下功能：

heapq.heappush(heap, item)

将值项推入堆中，保持堆不变。

heapq.heappop(heap)

弹出并返回堆中的最小项，保持堆不变。如果堆是空的，IndexError则升起。要访问最小的物品而不弹出它，请使用heap[0]。

heapq.heappushpop(heap, item)

按下堆上的项目，然后弹出并从堆中返回最小的项目。联合行动的运行效率比heappush()单独呼叫后的效率要高heappop()。

2.6版本中的新功能。

heapq.heapify(x)

在线性时间内将列表x转换为堆。

heapq.heapreplace(heap, item)

弹出并返回堆中最小的项目，并推送新项目。堆大小不会改变。如果堆是空的，IndexError则升起。

这一步操作比heappop()后面的步骤更有效heappush()，在使用固定大小的堆时更为合适。pop / push组合总是从堆中返回一个元素，并用item替换它。

返回的值可能会大于添加的项目。如果不需要，请考虑使用heappushpop()。它的push / pop组合返回两个值中较小的一个，在堆上留下较大的值。

该模块还提供了三种基于堆的通用功能。

heapq.merge(*iterables)

将多个排序后的输入合并到一个排序后的输出中（例如，合并来自多个日志文件的时间戳条目）。返回排序后的值的迭代器。

与sorted(itertools.chain(*iterables))返回iterable 类似，不会一次将数据拉入内存，并假定每个输入流已经排序（从最小到最大）。

New in version 2.6.

heapq.nlargest(n, iterable[, key])

返回由iterable定义的数据集中n个最大元素的列表。键（如果提供）指定一个参数的函数，该参数用于从迭代器中的每个元素提取比较键：等同于：key=str.lowersorted(iterable, key=key, reverse=True)[:n]

2.4版本中的新功能。

在版本2.5中更改：添加了可选的键参数。

heapq.nsmallest(n, iterable[, key])

返回由iterable定义的数据集中n个最小元素的列表。键（如果提供）指定一个参数的函数，该参数用于从迭代器中的每个元素提取比较键：等同于：key=str.lowersorted(iterable, key=key)[:n]

2.4版本中的新功能。

在版本2.5中更改：添加了可选的键参数。

后两个函数对于较小的n值表现最好。对于较大的值，使用该sorted()函数会更有效。另外，何时n==1使用内置函数min()和max()函数更有效。如果需要重复使用这些函数，请考虑将迭代器转换为实际的堆。

1.基本例子

甲堆排序可以通过按所有值到堆，然后突然离开在时刻的最小值的一个来实现：

>>> def heapsort(iterable):
...     h = []
...     for value in iterable:
...         heappush(h, value)
...     return [heappop(h) for i in range(len(h))]
...
>>> heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

这与此类似sorted(iterable)，但与sorted()此不同，此实现不稳定。

堆元素可以是元组。这对于在跟踪的主要记录旁边分配比较值（例如任务优先级）很有用：

>>> h = []
>>> heappush(h, (5, 'write code'))
>>> heappush(h, (7, 'release product'))
>>> heappush(h, (1, 'write spec'))
>>> heappush(h, (3, 'create tests'))
>>> heappop(h)
(1, 'write spec')

2.优先队列实施注释

一个优先级队列是堆共同使用，并呈现一些执行方面的挑战：

• 排序稳定性：如何获得具有相同优先级的两个任务，按照它们最初添加的顺序返回？

• 在将来使用Python 3时，如果优先级相等且任务没有默认比较顺序，则元组比较会中断（优先级，任务）对。

• 如果任务的优先级发生变化，您如何将其移至堆中的新位置？

• 或者如果需要删除待处理任务，您如何找到并将其从队列中删除？

前两个挑战的解决方案是将条目存储为3元素列表，包括优先级，条目计数和任务。输入计数用作决胜因此具有相同优先级的两个任务按照它们添加的顺序返回。由于没有两个入口计数是相同的，所以元组比较决不会直接比较两个任务。

剩下的挑战围绕着寻找未决任务和改变优先级或完全移除它。查找任务可以通过指向队列中的条目的字典完成。

删除条目或改变其优先级更困难，因为它会打破堆结构不变量。因此，一种可能的解决方案是将现有条目标记为已删除，并添加一个新条目并修改优先级：

pq = []                         # list of entries arranged in a heap
entry_finder = {}               # mapping of tasks to entries
REMOVED = '<removed-task>'      # placeholder for a removed task
counter = itertools.count()     # unique sequence count

def add_task(task, priority=0):
    'Add a new task or update the priority of an existing task'
    if task in entry_finder:
        remove_task(task)
    count = next(counter)
    entry = [priority, count, task]
    entry_finder[task] = entry
    heappush(pq, entry)

def remove_task(task):
    'Mark an existing task as REMOVED.  Raise KeyError if not found.'
    entry = entry_finder.pop(task)
    entry[-1] = REMOVED

def pop_task():
    'Remove and return the lowest priority task. Raise KeyError if empty.'
    while pq:
        priority, count, task = heappop(pq)
        if task is not REMOVED:
            del entry_finder[task]
            return task
    raise KeyError('pop from an empty priority queue')

理论

堆是数组a[k] <= a[2*k+1]，a[k] <= a[2*k+2]对于所有k，计数从0开始的元素。为了比较，不存在的元素被认为是无限的。堆的有趣属性是它a[0]始终是其最小的元素。

上面这个奇怪的不变性意味着成为比赛的高效内存表示。下面的数字是k，而不是a[k]：

                               0

              1                                 2

      3               4                5               6

  7       8       9       10      11      12      13      14

15 16   17 18   19 20   21 22   23 24   25 26   27 28   29 30

在上面的树中，每个单元格k都在顶部2*k+1和顶部2*k+2。在我们通常看到的体育双星比赛中，每个单元格都是两个单元格上的赢家，我们可以在树上追踪赢家，看看他/她拥有的所有对手。但是，在这样的锦标赛的许多计算机应用程序中，我们不需要追踪获胜者的历史。为了提高记忆效率，当获胜者晋升时，我们试图用低级别的东西替代它，规则变成了一个单元格和它的两个单元格包含三个不同的项目，但顶级单元格“胜利”在两个顶部的单元格上。

如果这个堆不变量始终受到保护，那么索引0显然是总体赢家。最简单的算法去除它并找到“下一个”获胜者是将一些输家（比如上图中的单元格30）移动到0位置，然后将这个新的0渗透到树的下方，交换数值，直到不变量重新建立。这对树中的项目总数显然是对数的。通过迭代所有项目，您将得到一个O（n log n）排序。

这种排序的一个很好的特点是，如果插入的项目不比你提取的最后一个元素“更好”，你可以在排序进行时有效地插入新项目。这在模拟上下文中特别有用，其中树保存所有传入事件，“胜利”条件意味着最短的预定时间。当一个事件安排其他事件执行时，它们将被安排在将来，以便它们可以轻松地进入堆中。所以，堆是实现调度程序的好结构（这是我用于MIDI定序器的:-)。

实施调度程序的各种结构已经得到广泛研究，堆对此有好处，因为它们速度相当快，速度几乎不变，最坏的情况与平均情况相差不大。但是，还有其他表述总体上更有效率，但最糟糕的情况可能会很糟糕。

堆在大磁盘排序中也非常有用。你很可能都知道，大的排序意味着产生“运行”（这是预先排序的序列，其大小通常与CPU内存的数量有关），然后是这些运行的合并过程，合并通常非常巧妙有组织[1]。初始排序产生尽可能最长的运行是非常重要的。锦标赛是实现这一目标的好方法。如果使用所有可用的内存来举办锦标赛，您将替换并渗透恰好与当前运行相匹配的项目，您将生成运行内存大小为随机输入大小的两倍，并且对于模糊排序的输入更好。

此外，如果您在磁盘上输出第0个项目，并获得可能不适合当前锦标赛的输入（因为值“胜过”最后一个输出值），它无法放入堆中，所以堆减少。释放的内存可以被巧妙地重复使用，以逐步构建第二堆，第一堆的堆积速度与第一堆堆积的速度完全相同。当第一个堆完全消失时，您切换堆并开始新的运行。聪明，相当有效！

总而言之，堆是知道有用的内存结构。我在一些应用程序中使用它们，我认为保持'堆'模块是很好的。:-)

注