`heapq` ---堆队列算法¶

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

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

下面的API与教科书堆算法有两个不同之处：（a）我们使用的是基于零的索引。这使得节点的索引与其子节点的索引之间的关系稍显不明显，但由于Python使用了基于零的索引，因此更适合这种关系。（B）我们的pop方法返回的是最小的项，而不是最大的项（在教科书中称为“最小堆”；“最大堆”在文本中更常见，因为它适合就地排序）。

这两种方法可以将堆作为常规的python列表查看，而不会产生意外： heap[0] 是最小的项目，并且 heap.sort() 保持堆不变！

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

提供以下功能：

heapq.heappush(heap, item)¶: 推值 item 上 heap ，保持堆不变。

heapq.heappop(heap)¶: 弹出并返回 heap ，保持堆不变。如果堆是空的， IndexError 提高了。要在不弹出的情况下访问最小的项目，请使用 heap[0] .

heapq.heappushpop(heap, item)¶: 推 item 在堆中，然后弹出并返回 heap . 联合行动比 heappush() 然后单独调用 heappop() .

heapq.heapify(x)¶: 转换列表 x 成堆，在适当的地方，在线性时间。

heapq.heapreplace(heap, item)¶

弹出并返回 heap 以及推动新的 item . 堆大小不变。如果堆是空的， IndexError 提高了。

这一步操作比 heappop() 然后 heappush() 并且在使用固定大小的堆时更合适。pop/push组合始终返回堆中的元素，并将其替换为 item .

返回的值可能大于 item 补充。如果不需要，请考虑使用 heappushpop() 相反。它的push/pop组合返回两个值中较小的值，将较大的值留在堆中。

该模块还提供了三个基于堆的通用函数。

heapq.merge(*iterables, key=None, reverse=False)¶

将多个已排序的输入合并为一个已排序的输出（例如，合并多个日志文件中的时间戳项）。返回一个 iterator 在排序后的值上。

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

有两个可选参数，必须指定为关键字参数。

key 指定一个 key function 用于从每个输入元素中提取比较键的参数。默认值为 None （直接比较元素）。

reverse 是布尔值。如果设置为 True ，然后合并输入元素，就好像每个比较都是相反的。实现类似于 sorted(itertools.chain(*iterables), reverse=True) ，所有iterables必须从最大到最小排序。

在 3.5 版更改: 添加了可选的 key 和 reverse 参数。

heapq.nlargest(n, iterable, key=None)¶: 返回带有 n 数据集中最大的元素由定义 可迭代的 . key 如果提供，则指定一个参数的函数，该参数用于从中的每个元素提取比较键。 可迭代的 （例如， key=str.lower ）相当于： sorted(iterable, key=key, reverse=True)[:n] .

heapq.nsmallest(n, iterable, key=None)¶: 返回带有 n 数据集中的最小元素由定义 可迭代的 . key 如果提供，则指定一个参数的函数，该参数用于从中的每个元素提取比较键。 可迭代的 （例如， key=str.lower ）相当于： sorted(iterable, key=key)[:n] .

后两个函数对较小的 n . 对于较大的值，使用 sorted() 功能。此外，当 n==1 ，使用内置的 min() 和 max() 功能。如果需要重复使用这些函数，请考虑将ITerable转换为实际的堆。

基本实例¶

A heapsort 可以通过将所有值推送到一个堆上，然后一次弹出一个最小值来实现：

>>> 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')

优先级队列实现说明¶

A priority queue 是堆的常见用途，它带来了几个实现挑战：

排序稳定性：如何使两个优先级相同的任务按最初添加的顺序返回？
如果优先级相等且任务没有默认的比较顺序，则为（优先级、任务）对中断元组比较。
如果任务的优先级改变，如何将其移动到堆中的新位置？
或者，如果一个挂起的任务需要删除，您如何找到它并将其从队列中删除？

前两个挑战的解决方案是将条目存储为三元素列表，包括优先级、条目计数和任务。条目计数充当一个连接断路器，以便按照添加它们的顺序返回具有相同优先级的两个任务。由于没有两个条目计数相同，所以元组比较永远不会尝试直接比较两个任务。

解决不可比较任务问题的另一个解决方案是创建一个封装类，该类忽略任务项并只比较优先级字段：

from dataclasses import dataclass, field
from typing import Any

@dataclass(order=True)
class PrioritizedItem:
    priority: int
    item: Any=field(compare=False)

剩下的挑战围绕着找到一个悬而未决的任务，改变它的优先级或者完全删除它。查找任务可以通过指向队列中某个条目的字典来完成。

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

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）排序。

这种排序的一个很好的特性是，如果插入的项不比您提取的最后0个元素“更好”，则可以在排序过程中有效地插入新项。这在模拟环境中特别有用，在模拟环境中，树包含所有传入事件，“赢”条件意味着最小的计划时间。当一个事件为执行而调度其他事件时，它们将被调度到将来，因此它们可以很容易地进入堆中。因此，堆是实现调度程序的良好结构（这是我在midi sequencer中使用的结构：-）。

对于实现调度程序的各种结构已经进行了广泛的研究，堆有利于实现这一点，因为它们的速度相当快，速度几乎是恒定的，最坏的情况与平均情况没有太大的不同。然而，总的来说，还有其他更有效的表示，但最坏的情况可能是可怕的。

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

此外，如果您在磁盘上输出第0个项目，并得到一个可能不适合当前锦标赛的输入（因为值“赢”于最后一个输出值），则它不能适合堆，因此堆的大小会减小。释放的内存可以被巧妙地立即重用，以逐步构建第二个堆，其增长速度与第一个堆正在融化的速度完全相同。当第一个堆完全消失时，您切换堆并开始新的运行。聪明而且相当有效！

总之，堆是有用的内存结构。我在一些应用程序中使用它们，我认为保留一个“堆”模块比较好。-）

脚注

1: 目前流行的磁盘平衡算法比聪明的算法更烦人，这是磁盘搜索能力的结果。在无法寻找的设备上，比如大型磁带机，情况就大不一样了，必须非常聪明，以确保（提前）每个磁带移动都是最有效的（也就是说，最好参与“进行”合并）。有些磁带甚至可以倒读，这也被用来避免倒带时间。相信我，真正好的磁带种类是相当壮观的观看！从古至今，分类一直是一门伟大的艺术！-）

`heapq` ---堆队列算法¶

基本实例¶

优先级队列实现说明¶

理论¶

Table of Contents

上一个主题

下一个主题

heapq ---堆队列算法¶

基本实例¶

优先级队列实现说明¶

理论¶

`heapq` ---堆队列算法¶