Python heapq 模块：使用堆和优先级队列

数据结构、堆和优先级队列

抽象数据结构指定操作和它们之间的关系。例如，优先级队列抽象数据结构支持三种操作：

1. is_empty检查队列是否为空。
2. add_element向队列添加一个元素。
3. pop_element弹出具有最高优先级的元素。

优先级队列通常用于优化任务执行，其目标是处理具有最高优先级的任务。任务完成后，其优先级降低，并返回到队列中。

确定元素的优先级有两种不同的约定：

1. 在最大的元素具有最高优先级。
2. 在最小的元素具有最高优先级。

这两个约定是等效的，因为您始终可以颠倒有效顺序。例如，如果您的元素由numbers组成，那么使用负数将改变约定。

Pythonheapq模块使用第二个约定，通常是两者中比较常见的一个。在这个约定下，最小的元素具有最高的优先级。这听起来可能令人惊讶，但通常非常有用。在您稍后将看到的实际示例中，此约定将简化您的代码。

具体数据结构实现抽象数据结构中定义的操作，并进一步指定性能保证。

优先级队列的堆实现保证推送（添加）和弹出（移除）元素都是对数时间操作。这意味着执行 push 和 pop 所需的时间与元素数量的以2为底的对数成正比。

对数增长缓慢。15 的以 2 为底的对数约为 4，而万亿的以 2 为底的对数约为 40。这意味着如果一个算法在 15 个元素上足够快，那么它在 1 万亿个元素上只会慢十倍，而且可能仍然足够快。

在任何关于性能的讨论中，最大的警告是这些抽象的考虑没有实际衡量一个具体的程序和了解瓶颈所在的意义。一般性能保证对于对程序行为做出有用的预测仍然很重要，但应该确认这些预测。

堆的实现

堆将优先队列实现为一棵完整的二叉树。在二叉树中，每个节点最多有两个孩子。在完整的二叉树中，除了可能最深的一层之外，所有层都一直是满的。如果最深层次是不完整的，那么它将具有尽可能向左的节点。

的完整性属性意味着该树的深度为元件的数量的基2对数，向上舍入。下面是一个完整的二叉树的例子：

堆作为 Pythonheapq模块中的列表

尽管您之前将堆描述为一棵树，但重要的是要记住它是一棵完整的二叉树。完整性意味着总是可以知道除了最后一层之外每一层有多少元素。因此，堆可以实现为列表。这就是 Pythonheapq模块所做的。

确定索引处的元素k与其周围元素之间的关系有三个规则：

1. 它的第一个孩子在2*k + 1。
2. 它的第二个孩子在2*k + 2。
3. 它的父级位于(k - 1) // 2。

上面的规则告诉您如何将列表可视化为完整的二叉树。请记住，元素总是有父元素，但有些元素没有子元素。如果2*k超出列表末尾，则该元素没有任何子元素。如果2*k + 1是有效索引但2*k + 2不是，则该元素只有一个子元素。

heap 属性意味着如果h是堆，则以下内容永远不会是False：

h[k] <= h[2*k + 1] and h[k] <= h[2*k + 2]

IndexError如果任何索引超出列表的长度，它可能会引发，但它永远不会是False。

换句话说，元素必须始终小于其索引加一和索引加二的两倍处的元素。

这是满足堆属性的列表的视觉效果：

基本操作

Pythonheapq模块在列表上实现堆操作。与许多其他模块不同，它没有定义自定义类。Pythonheapq模块具有直接处理列表的函数。

通常，如上面的电子邮件示例，元素将一个一个地插入到一个堆中，从一个空堆开始。但是，如果已经有一个元素列表需要成为堆，那么 Pythonheapq模块包括heapify()将列表转换为有效堆。

下面的代码使用heapify()转a成堆：

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]

您可以检查即使7在 之后8，列表a仍然遵守堆属性。例如，a[2]，即3，小于a[2*2 + 2]，即7。

如您所见，heapify()就地修改列表但不对其进行排序。不必对堆进行排序以满足堆属性。但是，由于每个排序列表都满足堆属性，因此heapify()在排序列表上运行不会更改列表中元素的顺序。

Pythonheapq模块中的其他基本操作假定列表已经是一个堆。需要注意的是，空列表或长度为 1 的列表将始终是一个堆。

由于树的根是第一个元素，因此您不需要专用函数来无损读取最小元素。第一个元素 ,a[0]将始终是最小的元素。

为了在保留堆属性的同时弹出最小元素，Pythonheapq模块定义了heappop().

以下是如何使用heappop()弹出元素：

>>> import heapq
>>> a = [1, 2, 3, 5, 6, 8, 7]
>>> heapq.heappop(a)
1
>>> a
[2, 5, 3, 7, 6, 8]

该函数返回第一个元素 ，1并保留 上的堆属性a。例如，a[1]is5和a[1*2 + 2]is 6。

Pythonheapq模块还包括heappush()用于将元素推送到堆，同时保留堆属性。

以下示例显示将值推送到堆：

>>> import heapq
>>> a = [2, 5, 3, 7, 6, 8]
>>> heapq.heappush(a, 4)
>>> a
[2, 5, 3, 7, 6, 8, 4]
>>> heapq.heappop(a)
2
>>> heapq.heappop(a)
3
>>> heapq.heappop(a)
4

推4入堆后，从中弹出三个元素。由于2和3已经在堆中并且小于4，它们首先被弹出。

Pythonheapq模块还定义了另外两个操作：

1. heapreplace()相当于heappop()后面跟着heappush()。
2. heappushpop()相当于heappush()后面跟着heappop()。

这些在某些算法中很有用，因为它们比单独执行两个操作更有效。

堆可以解决的问题

正如您在上面看到的，堆非常适合增量合并已排序的序列。您已经考虑过的两个堆应用程序是调度周期性任务和合并日志文件。然而，还有更多的应用。

堆还可以帮助识别顶部n或底部n事物。Pythonheapq模块具有实现此行为的高级函数。

例如，此代码获取2016 年夏季奥运会女子 100 米决赛的时间作为输入，并打印奖牌获得者或前三名：

>>> import heapq
>>> results="""\
... Christania Williams      11.80
... Marie-Josee Ta Lou       10.86
... Elaine Thompson          10.71
... Tori Bowie               10.83
... Shelly-Ann Fraser-Pryce  10.86
... English Gardner          10.94
... Michelle-Lee Ahye        10.92
... Dafne Schippers          10.90
... """
>>> top_3 = heapq.nsmallest(
...     3, results.splitlines(), key=lambda x: float(x.split()[-1])
... )
>>> print("\n".join(top_3))
Elaine Thompson          10.71
Tori Bowie               10.83
Marie-Josee Ta Lou       10.86

此代码使用nsmallest()来自 Pythonheapq模块。nsmallest()返回可迭代对象中的最小元素并接受三个参数：

1. n 指示要返回多少个元素。
2. iterable 标识要比较的元素或数据集。
3. key 是一个可调用的函数，用于确定如何比较元素。

在这里，该key函数用空格分割行，获取最后一个元素，并将其转换为浮点数。这意味着代码将按运行时间对行进行排序，并返回运行时间最短的三行。这些对应于三个最快的跑步者，它为您提供金牌、银牌和铜牌获得者。

Pythonheapq模块还包括nlargest()，它具有类似的参数并返回最大的元素。如果您想从标枪比赛中获得奖牌，这将非常有用，该比赛的目标是将标枪投得尽可能远。

如何识别问题

堆作为优先队列的实现，是解决涉及极端问题的好工具，例如给定度量的最多或最少。

还有其他词表明堆可能有用：

• Largest
• Smallest
• Biggest
• Smallest
• Best
• Worst
• Top
• Bottom
• Maximum
• Minimum
• Optimal
  

每当问题陈述表明您正在寻找某些极端元素时，就值得考虑优先队列是否有用。

有时优先级队列只是解决方案的一部分，其余部分将是动态编程的一些变体。您将在下一节中看到的完整示例就是这种情况。动态规划和优先级队列通常一起使用。

顶级代码

现在您了解了算法，是时候编写代码来实现它了。在实现算法本身之前，编写一些支持代码很有用。

首先，您需要导入Pythonheapq模块：

import heapq

您将使用 Pythonheapq模块中的函数来维护一个堆，该堆将帮助您在每次迭代中找到具有最短已知路径的位置。

下一步是在代码中将地图定义为变量：

map = """\
.......X..
.......X..
....XXXX..
..........
..........
"""

该地图是一个三引号字符串，显示机器人可以移动的区域以及任何障碍物。

虽然更现实的场景是让您从文件中读取地图，但出于教学目的，使用此简单地图在代码中定义变量会更容易。该代码适用于任何地图，但在简单地图上更易于理解和调试。

该地图经过优化，便于代码的人类读者理解。点 ( .) 足够轻，看起来是空的，但它的优点是可以显示允许区域的尺寸。这些X位置标记了机器人无法通过的障碍物。

核心算法代码

回顾一下，您正在寻找起点和终点之间的最短路径。

您保留三部分数据：

1. certain 是某些位置的集合。
2. candidates 是一堆候选人。
3. tentative 是将节点映射到当前最短已知路径的字典。

certain如果您可以确定最短的已知路径是最短的可能路径，那么位置就在。如果目的地在certain集合中，那么到目的地的最短已知路径无疑是最短的可能路径，您可以返回此路径。

的堆candidates按已知最短路径的长度组织，并在 Pythonheapq模块中的函数的帮助下进行管理。

在每一步，您都会查看已知路径最短的候选者。这是堆被弹出的地方heappop()。没有到这个候选的更短的路径——所有其他路径都经过 中的某个其他节点candidates，并且所有这些路径都更长。因此，可以标记当前候选人certain。

然后查看所有未访问的邻居，如果通过当前节点是一种改进，则使用 将它们添加到candidates堆中heappush()。

该函数find_path()实现了这个算法：

 1def find_path(map):
 2    lines, origin, destination = parse_map(map)
 3    tentative = {origin: []}
 4    candidates = [(0, origin)]
 5    certain = set()
 6    while destination not in certain and len(candidates) > 0:
 7        _ignored, current = heapq.heappop(candidates)
 8        if current in certain:
 9            continue
10        certain.add(current)
11        neighbors = set(get_neighbors(lines, current)) - certain
12        shorter = get_shorter_paths(tentative, neighbors, current)
13        for neighbor, path in shorter:
14            tentative[neighbor] = path
15            heapq.heappush(candidates, (len(path), neighbor))
16    if destination in tentative:
17        return tentative[destination] + [destination]
18    else:
19        raise ValueError("no path")

find_path()接收 amap作为字符串，并以位置列表的形式返回从起点到终点的路径。

这个函数有点长和复杂，所以让我们一点一点地浏览它：

• 第 2 行到第 5 行设置循环将查看和更新​​的变量。你已经知道一条从原点到自身的路径，它是长度为 0 的空路径。

• 第 6 行定义了循环的终止条件。如果没有candidates，则无法缩短任何路径。如果destination在 中certain，则destination无法缩短到 的路径。

• 第 7 行到第 10 行使用 获取候选者heappop()，如果它已经在 中certain，则跳过循环，否则将候选者添加到 中certain。这可确保每个候选对象最多被循环处理一次。

• 第 11 行到第 15 行使用get_neighbors()和get_shorter_paths()查找到相邻位置的较短路径并更新tentative字典和candidates堆。

• 第 16 到 19 行处理返回正确的结果。如果找到路径，则函数将返回它。虽然在没有最终位置的情况下计算路径使得算法的实现更简单，但将它与目的地一起返回是一个更好的 API 。如果未找到路径，则会引发异常。

将函数分解成不同的部分可以让您一次理解一个部分。

可视化代码

如果该算法实际上被机器人使用，那么机器人可能会通过它应该经过的位置列表表现得更好。但是，为了使结果更适合人类，将它们可视化会更好。

show_path() 在地图上绘制路径：

def show_path(path, map):
    lines = map.splitlines()
    for x, y in path:
        lines[y] = lines[y][:x] + "@" + lines[y][x + 1 :]
    return "\n".join(lines) + "\n"

该函数将path和map作为参数。它返回一个新地图，其路径由 at 符号 ( "@")指示。

运行代码

最后，您需要调用函数。这可以通过Python 交互式解释器来完成。

以下代码将运行算法并显示漂亮的输出：

>>> path = find_path(map)
>>> print(show_path(path, map))
@@.....X..
..@....X..
...@XXXX..
....@@@@@.
.........@

首先你得到最短路径find_path()。然后将其传递show_path()给以渲染带有标记路径的地图。最后，您print()将映射到标准输出。

路径向右移动一步，然后向右下角移动几步，然后向右移动几步，最后以向右下角的对角线移动结束。

恭喜！您已经使用 Pythonheapq模块解决了一个问题。

此类寻路问题可通过动态编程和优先级队列的组合解决，在求职面试和编程挑战中很常见。例如，2019 年的 Advent of Code包含了一个可以用这里描述的技术解决的问题。