8.4. heapq —堆队列算法

2.3 版的新Function。

源代码： Lib/heapq.py

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

堆是二叉树，其每个父节点的值都小于或等于其任何子节点。此实现对所有* 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()保持堆不变！

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

提供以下Function：

  • heapq. heappush(* heap ， item *)

    • 将值* item 推入 heap *，保持堆不变。

  • heapq. heappop(* heap *)

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

  • heapq. heappushpop(* heap ， item *)

    • 将* item 推入堆，然后弹出并从 heap *中返回最小的项。组合的动作比heappush()更有效地运行，随后分别调用heappop()。

2.6 版的新Function。

  • heapq. heapify(* x *)

    • 将列表* x *在线性时间内原位转换为堆。

  • heapq. heapreplace(* heap ， item *)

    • 弹出并从* heap 中返回最小的项，然后推动新的 item *。堆大小不变。如果堆为空，则引发IndexError。

此一步操作比heappop()和heappush()效率更高，并且在使用固定大小的堆时可能更合适。 pop/push 组合始终返回堆中的一个元素，并将其替换为* item *。

返回的值可能大于添加的* item *。如果不希望这样做，请考虑改用heappushpop()。它的推/弹出组合返回两个值中较小的一个，而将较大的值保留在堆上。

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

  • heapq. merge(** iterables *)
    • 将多个排序的 Importing 合并到一个排序的输出中(例如，合并多个日志文件中带有时间戳的条目)。返回排序后的值的iterator。

与sorted(itertools.chain(*iterables))相似，但返回一个可迭代的对象，不会一次将数据全部拉入内存，并假定每个 Importing 流都已排序(最小到最大)。

2.6 版的新Function。

  • heapq. nlargest(* n ， iterable * [，* key *])
    • 从* iterable 定义的数据集中返回最大 n *个元素的列表。 * key *(如果提供)指定一个参数的函数，该函数用于从可迭代的每个元素中提取比较键：key=str.lower等效于：sorted(iterable, key=key, reverse=True)[:n]

2.4 版的新Function。

在版本 2.5 中进行了更改：添加了可选的* key *参数。

  • heapq. nsmallest(* n ， iterable * [，* key *])
    • 从* iterable 定义的数据集中返回一个 n *个最小元素的列表。 * key *(如果提供)指定一个参数的函数，该函数用于从可迭代的每个元素中提取比较键：key=str.lower等效于：sorted(iterable, key=key)[:n]

2.4 版的新Function。

在版本 2.5 中进行了更改：添加了可选的* key *参数。

后两个函数对于* n *的较小值表现最佳。对于较大的值，使用sorted()函数更有效。同样，当为n==1时，使用内置的min()和max()函数更为有效。如果需要重复使用这些Function，请考虑将可迭代对象转换为实际堆。

8.4.1. 基本范例

可以pass将所有值压入堆然后一次弹出一个最小值来实现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()不同，此实现不稳定。

堆元素可以是 Tuples。这对于在跟踪主记录的同时分配比较值(例如任务优先级)很有用：

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

8.4.2. 优先队列实施说明

priority queue通常用于堆，它带来了一些实现方面的挑战：

  • 排序稳定性：如何使两个优先级相同的任务按最初添加的 Sequences 返回？

  • 在将来使用 Python 3 时，如果优先级相等并且任务没有默认的比较 Sequences，则 Tuples 比较会break(优先级，任务)对。

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

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

前两个挑战的解决方案是将条目存储为 3 元素列表，包括优先级，条目计数和任务。条目计数是一个平局，因此具有相同优先级的两个任务将按其添加 Sequences 返回。并且由于没有两个条目计数相同，因此 Tuples 比较将永远不会try直接比较两个任务。

剩下的挑战围绕寻找未完成的任务并更改其优先级或将其完全删除而进行。查找任务可以使用指向队列中条目的字典来完成。

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

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

8.4.3. Theory

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

上面的奇怪不变式是表示 match 的有效 Memory 形式。以下数字是* 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的顶部。在体育 match 中我们看到的通常的二元锦标赛中，每个单元格都是其顶部两个单元格的赢家，我们可以在树上追踪赢家，以查看所有对手。但是，在此类 match 的许多计算机应用程序中，我们不需要跟踪获胜者的历史。为了提高内存效率，当提升获胜者时，我们try用较低的其他等级替换它，规则变成一个单元格和其顶部的两个单元格包含三个不同的项目，但顶部的单元格“获胜”在两个顶部的单元格上。

如果这个堆不变式始终受到保护，则索引 0 显然是整体赢家。删除它并找到“下一个”获胜者的最简单算法是将一些失败者(上图中的单元格 30)移到 0 位置，然后将这个新的 0 渗透到树上，交换值，直到不变重新构建。这显然是树中项目总数的对数。pass遍历所有项，可以得到 O(n log n)排序。

这种分类的一个不错的Function是，只要插入的项目不比您提取的最后一个第 0 个元素“好”，就可以在进行分类时有效地插入新项目。这在仿真上下文中特别有用，在仿真上下文中，树包含所有传入事件，并且“获胜”条件表示最小的计划时间。当一个事件安排其他事件执行时，它们被安排在将来，因此可以轻松地进入堆。因此，堆是实现调度程序的好结构(这是我在 MIDI 音序器中使用的:-)。

广泛地研究了用于实现调度程序的各种结构，并且堆对于此有好处，因为它们相当快，速度几乎是恒定的，最坏的情况与平均情况没有太大区别。但是，还有其他一些表示在整体上更有效，但最坏的情况可能很糟糕。

在大磁盘类型中，堆也非常有用。大家可能都知道，大型排序意味着产生“运行”(它们是预先排序的序列，其大小通常与 CPU 内存量有关)，然后是这些运行的合并遍历，这种合并通常非常巧妙有组织的[1]。初始排序产生尽可能长的运行非常重要。match 是达成目标的好方法。如果使用所有可用的内存来举办 match，替换并渗入恰好适合当前 Running 的项目，那么您产生的 Running 的大小是随机 Importing 的两倍，而对于模糊排序的 Importing 则更好。

此外，如果您在磁盘上输出第 0 个项目并获得了可能不适合当前锦标赛的 Importing(因为值“胜过”了最后一个输出值)，则它无法容纳在堆中，因此，堆减少。可以立即巧妙地重用释放的内存，以逐步构建第二个堆，该堆的增长速度与第一个堆正在融化的速度完全相同。当第一个堆完全消失时，切换堆并开始新的运行。聪明又有效！

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

Footnotes

  • [1]
    • 如今，当前的磁盘平衡算法比聪明的算法更令人讨厌，这是磁盘寻求Function的结果。在无法寻找的设备(例如大型磁带机)上，情况大不相同，必须非常聪明地确保(提前)确保每次磁带移动都将是最有效的(也就是说，最好参加“合并”.某些磁带甚至可以向后读取，这也可以避免倒带时间.相信我，观看 true 的好磁带种类非常壮观！一直以来，分类一直是一门伟大的艺术！ :-)
Name Python 中文文档
Version
Language
Badge
Last Updated 2021-07-03T12:24:35