heapq-堆队列算法详解(34)Python语言(必读进阶学习教程)(参考资料)

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

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

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

这两个使得可以将堆视为常规Python列表而不会出现意外：heap[0]是最小的项目，并heap.sort()保持堆不变！

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

提供以下功能：

heapq.heappush（堆，项目）

将值项推送到堆上，保持堆不变。

heapq.heappop（堆）

弹出并返回堆中的最小项，保持堆不变。如果堆为空，IndexError则引发。要访问最小的项目而不弹出它，请使用heap[0]。

heapq.heappushpop（堆，项目）

在堆上推送项目，然后弹出并返回堆中的最小项目 。合并后的操作比heappush() 单独调用后更有效heappop()。

heapq.heapify（x ）

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

heapq.heapreplace（堆，项目）

弹出并返回堆中的最小项，并同时推送新项。堆大小不会改变。如果堆为空，IndexError则引发。

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

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

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

heapq.merge（* iterables，key = None，reverse = False ）

将多个已排序的输入合并为单个排序的输出（例如，合并来自多个日志文件的带时间戳的条目）。返回 排序值上的迭代器。

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

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

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

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

版本3.5中已更改：添加了可选键和反向参数。

heapq.nlargest（n，iterable，key = None ）

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

heapq.nsmallest（n，iterable，key = None ）

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

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

基本例子

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

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

优先级队列实现注释

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

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

前两个挑战的解决方案是将条目存储为3元素列表，包括优先级，条目计数和任务。条目计数用作打破平局，以便按添加顺序返回具有相同优先级的两个任务。由于没有两个条目计数是相同的，元组比较将永远不会尝试直接比较两个任务。

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

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

理论

堆是数组，对于所有 k，从0计数元素。为了比较，不存在的元素被认为是无限的。堆的有趣属性始终是它的最小元素。a[k] <= a[2*k+1]a[k] <= a[2*k+2]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个元素“更好”。这在模拟上下文中特别有用，其中树保存所有传入事件，“win”条件表示最小的调度时间。当事件安排其他事件执行时，它们将被安排到将来，因此它们可以轻松地进入堆。因此，堆是一个很好的结构来实现调度程序（这是我用于我的MIDI音序器:-)。

已经广泛研究了用于实现调度器的各种结构，并且堆很好，因为它们相当快速，速度几乎恒定，并且最坏情况与普通情况没有太大差别。但是，还有其他表示总体上更有效，但最糟糕的情况可能是可怕的。

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

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

总之，堆是有用的内存结构。我在一些应用程序中使用它们，我认为保持“堆”模块是件好事。:-)

脚注