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

举报
Yuchuan 发表于 2021/12/16 17:48:45 2021/12/16
【摘要】 您现在知道堆和优先级队列数据结构是什么以及它们在解决哪些类型的问题时很有用。您学习了如何使用 Pythonheapq模块将 Python 列表用作堆。您还学习了如何使用 Pythonheapq模块中的高级操作,例如merge()在内部使用堆的 。

目录

优先级队列是鲜为人知但非常有用的数据结构。对于涉及在数据集中寻找最佳元素的许多问题,它们提供了一种易于使用且高效的解决方案。Pythonheapq模块是标准库的一部分。它实现了所有低级堆操作以及堆的一些高级常见用途。

优先级队列是一个强大的工具,可以解决各种各样的问题,例如编写电子邮件调度程序、查找地图上的最短路径或合并日志文件。编程充满了优化问题,其目标是找到最佳元素。优先队列和 Pythonheapq模块中的函数通常可以帮助解决这个问题。

在本教程中,您将学习

  • 什么是优先级队列以及它们之间的关系
  • 使用堆可以解决什么样的问题
  • 如何使用Pythonheapq模块解决这些问题

本教程适用于熟悉列表字典集合生成器并正在寻找更复杂的数据结构的Pythonistas 。

什么是堆?

堆是具体的数据结构,而优先级队列是抽象的数据结构。抽象的数据结构决定了接口,而具体的数据结构定义了实现。

堆通常用于实现优先级队列。它们是最流行的用于实现优先队列抽象数据结构的具体数据结构。

具体的数据结构还规定了性能保证。性能保证定义了结构的大小和操作所花费的时间之间的关系。了解这些保证可以让您预测程序随着其输入大小的变化将花费多少时间。

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

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

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

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

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

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

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

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

注意: Python的heapq模块,和一般的堆数据结构,是设计为允许找到任何元件,除了最小的一个。对于按大小检索任何元素,更好的选择是二叉搜索树

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

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

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

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

堆的实现

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

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

满足堆性质的完全二叉树

在此特定示例中,所有级别均已完成。除了最深的节点之外,每个节点都有两个孩子。共有三个级别的七个节点。三是七的以 2 为底的对数,四舍五入。

在基本级别的单个节点称为节点。将树顶部的节点称为根节点似乎很奇怪,但这是编程和计算机科学中的常见约定。

堆中的性能保证取决于元素如何在树上上下渗透。这样做的实际结果是,堆中的比较次数是树大小的以 2 为底的对数。

注意:比较有时涉及使用.__lt__(). 与在堆中完成的其他操作相比,在 Python 中调用用户定义的方法是一个相对较慢的操作,因此这通常是瓶颈。

在堆树中,节点中的值始终小于其两个子节点。这称为堆属性。这与二叉搜索树不同,在二叉搜索树中,只有左节点会小于其父节点的值。

推送和弹出的算法都依赖于暂时违反堆属性,然后通过比较和替换单个分支来修复堆属性。

例如,要将一个元素推送到堆上,Python 会将新节点添加到下一个打开的槽中。如果底层未满,则将节点添加到底部的下一个空槽。否则,将创建一个新级别,然后将元素添加到新的底层。

添加节点后,Python 会将其与其父节点进行比较。如果违反了堆属性,那么节点和它的父节点会被切换,并且检查会再次从父节点开始。这一直持续到堆属性成立或到达根。

类似地,当弹出最小元素时,Python 知道,由于堆属性,该元素位于树的根部。它用最深层的最后一个元素替换该元素,然后检查是否违反了该分支的堆属性。

优先队列的使用

优先级队列和作为优先级队列实现的堆对于涉及寻找某种极端元素的程序很有用。例如,您可以将优先级队列用于以下任何任务:

  • 从点击数据中获取三个最受欢迎的博客文章
  • 寻找从一个点到另一个点的最快方式
  • 根据到站频率预测哪辆公交车最先到站

您可以使用优先级队列的另一项任务是安排电子邮件。想象一个系统有多种电子邮件,每种电子邮件都需要以特定频率发送。一种电子邮件需要每十五分钟发出一次,另一种需要每四十分钟发送一次。

调度程序可以将两种类型的电子邮件添加到队列中,并带有一个时间戳,指示下一次需要发送电子邮件的时间。然后调度器可以查看具有最小时间戳的元素——表明它是下一个要发送的元素——并计算在发送前休眠多长时间。

当调度器唤醒时,它会处理相关的电子邮件,将电子邮件从优先级队列中取出,计算下一个时间戳,并将电子邮件放回队列中的正确位置。

堆作为 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

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

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

堆实现为列表

箭头从元素k到元素2*k + 12*k + 2。例如,Python 列表中的第一个元素具有 index 0,因此它的两个箭头指向索引12。请注意箭头总是从较小的值变为较大的值。这是检查列表是否满足堆属性的方法。

基本操作

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]is5a[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入堆后,从中弹出三个元素。由于23已经在堆中并且小于4,它们首先被弹出。

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

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

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

高级操作

由于优先级队列经常用于合并已排序的序列,因此 Pythonheapq模块有一个现成的函数merge(),用于使用堆合并多个可迭代对象。merge()假设它的输入可迭代对象已经排序并返回一个迭代器,而不是一个列表。

作为 using 的示例merge(),这里是之前描述的电子邮件调度程序的实现:

import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)

merge()在这个例子中的输入是无限生成器。分配给变量 的返回值unified也是一个无限迭代器。这个迭代器将产生按照未来时间戳的顺序发送的电子邮件。

要调试并确认代码合并正确,您可以打印要发送的前十封电子邮件:

>>>
>>> for _ in range(10):
...    print(next(element))
(datetime.datetime(2020, 4, 12, 21, 27, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 21, 42, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 21, 52, 20, 305360), 'slow email')
(datetime.datetime(2020, 4, 12, 21, 57, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 12, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 27, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 32, 20, 305360), 'slow email')
(datetime.datetime(2020, 4, 12, 22, 42, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 57, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 23, 12, 20, 305358), 'fast email')

请注意如何fast email15分钟slow email安排一次40,每一次安排一次,并且电子邮件正确交错,以便按时间戳顺序排列。

merge()不读取所有输入,而是动态工作。即使两个输入都是无限迭代器,打印前十个项目也很快完成。

类似地,当用于合并诸如按时间戳排列的日志文件行之类的排序序列时,即使日志很大,这也会占用合理的内存量。

堆可以解决的问题

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

堆还可以帮助识别顶部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模块的实际用例。该示例将使用一种经典算法,作为其中的一部分,需要一个堆。您可以通过单击以下链接下载示例中使用的源代码:

获取源代码: 单击此处获取您将用于了解本教程中 Python heapq 模块的源代码

想象一个需要在二维迷宫中导航的机器人。机器人需要从位于左上角的原点到右下角的目的地。机器人的记忆中有迷宫的地图,所以它可以在出发前规划整个路径。

目标是让机器人尽快完成迷宫。

我们的算法是Dijkstra 算法的变体。在整个算法中保留和更新了三种数据结构:

  1. tentative是从原点到位置的暂定路径图pos。该路径称为暂定路径,因为它是已知的最短路径,但它可能会得到改进。

  2. certain是一组点,tentative映射的路径肯定是最短的可能路径。

  3. candidates是一堆有路径的位置。堆的排序键是路径的长度。

在每个步骤中,您最多执行四项操作:

  1. 从 中弹出一个候选人candidates

  2. 将候选人添加到certain集合中。如果候选人已经是certain集合的成员,则跳过接下来的两个动作。

  3. 找到到当前候选的最短已知路径。

  4. 对于当前候选的每个直接邻居,查看通过候选是否给出比当前tentative路径更短的路径。如果是这样,则使用此新路径更新tentative路径和candidates堆。

这些步骤循环运行,直到将目的地添加到certain集合中。当目的地在certain集合中时,你就完成了。算法的输出是tentative到目的地的路径,现在certain是最短的可能路径。

顶级代码

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

首先,您需要导入Pythonheapq模块:

import heapq

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

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

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

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

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

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

支持代码

第一个函数将映射转换为更易于在代码中解析的内容。parse_map()获取地图并对其进行分析:

def parse_map(map):
    lines = map.splitlines()
    origin = 0, 0
    destination = len(lines[-1]) - 1, len(lines) - 1
    return lines, origin, destination

该函数接受一个映射并返回一个包含三个元素的元组:

  1. 的列表 lines
  2. 这 origin
  3. 这 destination

这允许其余代码处理为计算机设计的数据结构,而不是为了人类的视觉扫描能力。

的列表lines可以通过(x, y)坐标索引。该表达式lines[y][x]将位置值作为两个字符之一返回:

  1. 点 ( ".")表示该位置为空白区域。
  2. 字母"X"表示该位置是障碍物。

当您想找到机器人可以占据的位置时,这将非常有用。

该函数is_valid()计算给定(x, y)位置是否有效:

def is_valid(lines, position):
    x, y = position
    if not (0 <= y < len(lines) and 0 <= x < len(lines[y])):
        return False
    if lines[y][x] == "X":
        return False
    return True

这个函数有两个参数:

  1. lines 是作为线列表的地图。
  2. position是作为指示(x, y)坐标的二元整数检查的位置。

要有效,位置必须在地图边界内,而不是障碍物。

该函数y通过检查lines列表的长度来检查是否有效。该函数接下来x通过确保它在内部来检查它是否有效lines[y]。最后,既然您知道两个坐标都在地图内,代码会通过查看此位置的角色并将该角色与 进行比较来检查它们是否不是障碍物"X"

另一个有用的助手是get_neighbors(),它可以找到一个位置的所有邻居:

def get_neighbors(lines, current):
    x, y = current
    for dx in [-1, 0, 1]:
        for dy in [-1, 0, 1]:
            if dx == 0 and dy == 0:
                continue
            position = x + dx, y + dy
            if is_valid(lines, position):
                yield position

该函数返回当前位置周围的所有有效位置。

get_neighbors()小心避免将位置标识为自己的邻居,但它确实允许对角邻居。这就是为什么至少有一个dx并且dy不能为零,但它们都非零也可以。

最后的辅助函数是get_shorter_paths(),它可以找到更短的路径:

def get_shorter_paths(tentative, positions, through):
    path = tentative[through] + [through]
    for position in positions:
        if position in tentative and len(tentative[position]) <= len(path):
            continue
        yield position, path

get_shorter_paths()生成through最后一步的路径比当前已知路径短的位置。

get_shorter_paths() 有三个参数:

  1. tentative 是一个将位置映射到已知最短路径的字典。
  2. positions 是您想要缩短路径的位置的迭代。
  3. through是一个位置,通过它,也许positions可以找到一条更短的路径。

假设是positions从 一步就可以到达 中的所有元素through

该函数get_shorter_paths()检查使用through作为最后一步是否会为每个位置创建更好的路径。如果没有到达某个位置的已知路径,则任何路径都更短。如果存在已知路径,则只有在其长度较短时才会生成新路径。为了使 APIget_shorter_paths()更容易使用,部分yield也是较短的路径。

所有辅助函数都被编写为纯函数,这意味着它们不修改任何数据结构,只返回值。这使得遵循核心算法变得更容易,该算法执行所有数据结构更新。

核心算法代码

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

您保留三部分数据:

  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"

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

运行代码

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

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

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

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

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

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

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

结论

您现在知道优先级队列数据结构是什么以及它们在解决哪些类型的问题时很有用。您学习了如何使用 Pythonheapq模块将 Python 列表用作堆。您还学习了如何使用 Pythonheapq模块中的高级操作,例如merge()在内部使用堆的 。

在本教程中,您学习了如何:

  • 使用Python模块中的低级函数heapq解决需要堆或优先级队列的问题
  • 使用Python模块中的高级函数heapq合并已排序的可迭代对象或查找可迭代对象中最大或最小的元素
  • 认识问题是堆和优先级队列可以帮助解决
  • 预测使用堆的代码的性能

凭借您对堆和 Pythonheapq模块的了解,您现在可以解决许多问题,其中的解决方案取决于找到最小或最大元素。要跟随您在本教程中看到的示例.

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200