在本章中，我们将讨论与图形相关的概念。图的概念来自数学的一个分支，称为图论。图用于解决许多计算问题。图是一种非线性数据结构。此结构通过沿其边连接一组节点或顶点来表示数据。与我们到目前为止所看到的数据结构相比，它是一个完全不同的数据结构，对图形的操作（例如，遍历）可能是非常规的。在本章中，我们将讨论许多与图相关的概念。此外，我们还将在本章后面讨论优先级队列和堆。
在本章结束时，您应该能够执行以下操作：
- 了解什么是图形
- 了解图形的类型及其组成
- 知道如何表示图形并遍历它
- 了解什么是优先级队列的基本概念
- 能够实现优先级队列
- 能够确定列表中的第 i个最小元素
本章讨论的所有源代码都在 GitHub 存储库的以下链接中提供：https://github.com/PacktPublishing/Hands-On-Data-Structures-and-Algorithms-with-Python-Second-Edition/tree/master/Chapter08 。
图是在顶点之间形成连接的一组顶点和边。在更正式的方法中，图G是顶点集V和边集E的有序对，在正式的数学表示法中称为G = (V, E)。
此处给出了一个图形示例：
让我们讨论一下图的一些重要定义：
-
节点或顶点：图形中的点或节点称为顶点，通常在图形中用点表示。在上图中，顶点或节点为A、B、C、D和E。
-
边：这是两个顶点之间的连接。连接A和B的线是上图中边的示例。
-
循环：当来自节点的边入射到自身时，该边形成循环。
-
顶点度数：入射到给定顶点上的边的总数称为该顶点的度数。例如，上图中的B顶点的度数为
4。 -
邻接：指任意两个节点之间的连接；因此，如果任意两个顶点或节点之间存在连接，则称它们彼此相邻。例如，C节点与A节点相邻，因为它们之间有一条边。
-
路径：任意两个节点之间的顶点和边序列表示从A顶点到B顶点的路径。例如，CABE表示从C节点到E节点的路径。
-
叶顶（也称悬垂顶点：一个顶点或节点如果正好有一个度，则称为叶顶或悬垂顶点。
图由节点之间的边表示。连接边可以被视为有向的或无向的。如果图中的连接边是无向的，则该图称为无向图；如果图中的连接边是有向的，则该图称为有向图。无向图只是将边表示为节点之间的直线。除了节点已连接的事实之外，没有关于节点之间关系的其他信息。例如，在下图中，我们展示了四个节点的无向图，A、B、C和D，它们使用边连接：
在有向图中，边提供关于图中任意两个节点之间连接方向的信息。如果说从节点A到B的边是定向的，那么该边（A、B将不等于该边（B、A。定向边绘制为带箭头的直线，箭头将指向边连接两个节点的任何方向。例如，在下图中，我们显示了一个有向图，其中许多节点使用有向边连接：
边的箭头决定流向。只能从A移动到B，如上图所示，不能从B移动到A。在有向图中，每个节点（或顶点）都有一个独立度和一个独立度。让我们看看这些是什么：
- 索引：进入图中某个顶点的边的总数称为该顶点的索引。例如，在前面的图中，E节点由于边缘CE进入E节点而具有
1索引。 - 向外度：图中某个顶点向外延伸的边的总数称为该顶点的向外度。例如，上图中的E节点有
2的出度，因为它有两条边EF和ED从该节点出。 - 孤立顶点：当节点或顶点的度数为零时，称为孤立顶点。 *** 源顶点：如果顶点的索引为零，则称为源顶点。例如，在前面的图中，A节点是源顶点。* 汇****顶点：如果某个顶点的出度为零，则该顶点为汇顶点。例如，在前面的图中，F节点是汇点顶点。**
**# 加权图
加权图是具有与图中的边关联的数值权重的图。它可以是有向图或无向图。此数值可能用于指示距离或成本，具体取决于图表的用途。让我们考虑一个例子。下图显示了从A节点到D节点的不同方式。您可以直接从A到D，也可以选择通过B和C，考虑到与每条边相关的权重是到下一个节点的行程的时间量（以分钟为单位）：
在本例中，AD和ABCD代表两条不同的路径。路径就是在两个节点之间通过的一系列边。沿着这些路径，您可以看到AD旅程需要40分钟，而ABCD旅程需要25分钟。如果唯一需要考虑的是时间，那么最好沿着ABCD路径行进，即使这可能是一条较长的路线。这里需要注意的一点是，边缘可以定向，并且可能包含其他信息（例如，所用时间、行进距离等）。
我们可以用与其他数据结构（如链表）类似的方式实现图形。对于图形，将边视为对象和节点是有意义的。与节点一样，边也可以包含额外的信息，因此有必要遵循特定的路径。图中的边可以使用不同节点之间的链接来表示；如果图中有一条有向边，我们可以用一个箭头从一个节点指向另一个节点来实现它，这很容易在节点类中用next或previous、parent或child来表示。
在 Python 中实现图形时，图形可以用两种主要形式表示。一种方法是使用邻接列表，另一种方法是使用邻接矩阵。让我们考虑一个例子，如下面的图表所示，开发图形的两种表示形式：
邻接列表存储所有节点，以及图形中直接连接到它们的其他节点。在图G中，如果两个节点A和B之间存在直接连接，则称它们为相邻节点。Python 中的list数据结构用于表示图形。列表的indices可用于表示图中的节点或顶点。
在每个索引处，存储该顶点的相邻节点。例如，考虑与前面所示的样本图对应的以下邻接表：
框中的数字表示顶点。0索引表示图的A顶点，其相邻节点为B和C。1索引表示图的B顶点，其相邻节点为E、C和A。类似地，图的其他顶点C、E和F用其相邻节点的2、3和4索引表示，如上图所示
使用list表示是相当严格的，因为我们缺乏直接使用顶点标签的能力。因此，dictionary数据结构更适合表示图形。要使用字典数据结构实现相同的上图，我们可以使用以下语句：
graph = dict()
graph['A'] = ['B', 'C']
graph['B'] = ['E','C', 'A']
graph['C'] = ['A', 'B', 'E','F']
graph['E'] = ['B', 'C']
graph['F'] = ['C'] 现在我们可以很容易地确定A顶点具有B和C的相邻顶点。F顶点将C顶点作为其唯一邻居。类似地，B顶点具有E、B和A的相邻顶点。
另一种表示图形的方法是使用邻接矩阵。矩阵是二维数组。这里的想法是用1或0表示单元，这取决于两个顶点是否通过边连接。我们在下图中演示了一个示例图及其相应的邻接矩阵：
邻接矩阵可以使用给定的邻接列表来实现。为了实现邻接矩阵，让我们采用前面基于字典的图实现。首先，我们必须获得邻接矩阵的关键元素。需要注意的是，这些矩阵元素是图的顶点。我们可以通过对图的键进行排序来获得关键元素。此操作的代码段如下所示：
matrix_elements = sorted(graph.keys())
cols = rows = len(matrix_elements) 接下来，使用图中键的长度来提供邻接矩阵的维数，邻接矩阵存储在cols和rows中，并且cols和rows中的值相等。然后我们通过rows为cols的数量创建一个大小正确的空邻接矩阵，并用零填充。edges_list变量将存储构成图中边的元组。例如，A 和 B 节点之间的边缘将被存储为(A, B)。初始化空邻接矩阵的代码段如下所示：
adjacency_matrix = [[0 for x in range(rows)] for y in range(cols)]
edges_list = []多维数组使用嵌套的for循环填充：
for key in matrix_elements:
for neighbor in graph[key]:
edges_list.append((key, neighbor)) 通过graph[key]获得顶点的邻域。然后，该键与neighbor组合用于创建存储在edges_list中的元组。
前面用于存储图形边缘的 Python 代码的输出如下所示：
>>> [('A', 'B'), ('A', 'C'), ('B', 'E'), ('B', 'C'), ('B', 'A'), ('C', 'A'),
('C', 'B'), ('C', 'E'), ('C', 'F'), ('E', 'B'), ('E', 'C'),
('F', 'C')]实现邻接矩阵的下一步是填充它，使用1表示图中存在边。这可以通过adjacency_matrix[index_of_first_vertex][index_of_second_vertex] = 1语句完成。标记图的边的完整代码片段如下所示
for edge in edges_list:
index_of_first_vertex = matrix_elements.index(edge[0])
index_of_second_vertex = matrix_elements.index(edge[1])
adjacency_matrix[index_of_first_vertex][index_of_second_vertex] = 1 matrix_elements数组有其rows和cols，从A开始到索引为0到5的所有其他顶点。for循环遍历我们的元组列表，并使用index方法获得存储边的相应索引。
前面代码的输出是前面显示的示例图的邻接矩阵。生成的邻接矩阵如下所示：
>>>
[0, 1, 1, 0, 0]
[1, 0, 0, 1, 0]
[1, 1, 0, 1, 1]
[0, 1, 1, 0, 0]
[0, 0, 1, 0, 0]在第1行和第1列，0表示 A 和 A 之间没有边。类似地，在第2列和第3行，有一个值1表示图中 C 和 B 顶点之间的边。
图遍历意味着访问图的所有顶点，同时跟踪哪些节点或顶点已被访问，哪些尚未被访问。如果图遍历算法能在尽可能短的时间内遍历图的所有节点，则该算法是有效的。图遍历的一种常见策略是沿着一条路径直到到达死角，然后向后遍历，直到有一点我们遇到另一条路径。我们还可以迭代地从一个节点移动到另一个节点，以便遍历整个图或其中的一部分。图遍历算法在回答许多基本问题时非常重要，它们可用于确定如何从图中的一个顶点到达另一个顶点，以及从图中的 a 到 B 顶点的路径优于其他路径。在下一节中，我们将讨论两种重要的图遍历算法：广度优先搜索（BFS）和深度优先搜索（DFS）。
广度优先遍历算法在图中按广度工作。队列数据结构用于存储图中要访问的顶点的信息。我们从起始节点开始，A节点。首先，我们访问该节点，然后查找其所有相邻顶点。我们首先逐个访问这些相邻顶点，同时将它们的邻居添加到要访问的顶点列表中。我们遵循这个过程，直到我们访问了图的所有顶点，确保没有顶点被访问两次。
让我们考虑一个例子来更好地理解图的广度优先遍历，使用下面的图表：
在上图中，我们在左侧有一个包含五个节点的图，在右侧有一个队列数据结构，用于存储要访问的顶点。我们开始访问第一个节点A，然后将其所有相邻顶点B、C和E添加到队列中。这里，需要注意的是，有多种方式将相邻节点添加到队列中，因为有三个节点，B、C和E，它们可以作为BCE、CEB、CBE、BEC 添加到队列中或ECB，每种方法都会给出不同的树遍历结果。
所有这些可能的图遍历解决方案都是正确的，但在本例中，我们将按字母顺序添加节点。访问A节点，如图所示：
一旦我们访问了A顶点，接下来，我们将访问其第一个相邻顶点B，并添加尚未添加到队列中或未访问的相邻顶点。在这种情况下，我们必须将D顶点添加到队列中：
现在，在访问了B顶点之后，我们访问了队列中的下一个顶点C顶点。再次添加尚未添加到队列中的相邻顶点。在这种情况下，没有剩余的未记录顶点，因此无需执行任何操作：
访问C顶点后，我们访问队列中的下一个顶点E顶点：
同样，在访问E顶点后，我们在最后一步访问D顶点：
因此，用于遍历前面图形的 BFS 算法按照A-B-C-E-D的顺序访问顶点。对于前面的图，这是 BFS 遍历的可能解决方案之一，但是我们可以得到许多可能的解决方案，这取决于我们如何将相邻节点添加到队列中。
为了学习在 Python 中实现该算法，让我们考虑一个无向图的另一个例子。
图表的邻接列表如下所示：
graph = dict()
graph['A'] = ['B', 'G', 'D']
graph['B'] = ['A', 'F', 'E']
graph['C'] = ['F', 'H']
graph['D'] = ['F', 'A']
graph['E'] = ['B', 'G']
graph['F'] = ['B', 'D', 'C']
graph['G'] = ['A', 'E']
graph['H'] = ['C'] 要使用宽度优先算法遍历此图，我们将使用队列。该算法创建一个列表来存储遍历过程中访问过的顶点。我们将从A节点开始遍历。
A节点排队并添加到已访问节点列表中。然后，我们使用一个while循环来实现图的遍历。在while循环中，A 节点退出队列。其未访问的相邻节点 B、G 和 D 按字母顺序排序并排队。队列现在将包含 B、D 和 G 节点。这些节点也将添加到已访问节点的列表中。此时，我们开始while循环的另一次迭代，因为队列不是空的，这也意味着我们没有真正完成遍历。
B 节点已退出队列。在其相邻节点 A、F 和 E 中，节点 A 已被访问。因此，我们只按字母顺序排列 E 和 F 节点。然后将 E 和 F 节点添加到已访问节点的列表中。
现在，我们的队列在这一点上包含以下节点：D、G、E 和 F。访问的节点列表包含 A、B、D、G、E 和 F。
D 节点已退出队列，但其所有相邻节点都已被访问，因此我们只需将其退出队列。队列前面的下一个节点是 G。我们将 G 节点出列，但我们还发现它的所有相邻节点都已被访问，因为它们位于已访问节点列表中。因此，G 节点也将退出队列。我们也将 E 节点出列，因为它的所有节点都已被访问。现在队列中唯一的节点是 F 节点。
F 节点是出列的，我们意识到在其相邻的节点 B、D 和 C 中，只有 C 没有被访问。然后，我们将 C 节点排队，并将其添加到访问的节点列表中。然后，将 C 节点从队列中退出。C 有 F 和 H 的相邻节点，但 F 已经被访问，离开 H 节点。H 节点排队并添加到访问节点列表中。
最后，while循环的最后一次迭代将导致 H 节点退出队列。它唯一的相邻节点 C 已经被访问过。一旦队列完全为空，循环就会中断。
图中图形的遍历输出是 A、B、D、G、E、F、C 和 H。
BFS 的代码如下所示：
from collections import deque
def breadth_first_search(graph, root):
visited_vertices = list()
graph_queue = deque([root])
visited_vertices.append(root)
node = root
while len(graph_queue) > 0:
node = graph_queue.popleft()
adj_nodes = graph[node]
remaining_elements =
set(adj_nodes).difference(set(visited_vertices))
if len(remaining_elements) > 0:
for elem in sorted(remaining_elements):
visited_vertices.append(elem)
graph_queue.append(elem)
return visited_vertices When we want to find out whether a set of nodes are in the list of visited nodes, we use the remaining_elements = set(adj_nodes).difference(set(visited_vertices)) statement. This uses the set object's difference method to find the nodes that are in adj_nodes, but not in visited_vertices.
在最坏情况下，将遍历每个顶点或节点以及边，因此 BFS 算法的时间复杂度为O(|V| + |E|)，其中|V|为顶点或节点数，|E|为图中的边数。
顾名思义，DFS 算法在遍历其广度之前遍历图中任何特定路径的深度。因此，在兄弟节点之前先访问子节点。stack数据结构用于实现 DFS 算法。
我们首先访问一个节点，然后查看一个顶点的邻居，然后是该邻居的邻居，依此类推。让我们在 DFS 的上下文中考虑下面的图：
在访问了A顶点后，我们访问了它的一个邻居B，如图所示：
在访问了B顶点后，我们再看看A的另一个邻居，即S，因为没有连接到B的顶点可以访问。接下来，我们寻找S顶点的邻居，即C和G顶点。我们访问C如下：
访问C节点后，我们访问其相邻顶点D和E：
同样，在访问了E顶点后，我们访问了H和F顶点，如下图所示：
最后，我们访问F节点：
DFS 遍历的输出为A-B-S-C-D-E-H-G-F。
为了实现 DFS，我们从给定图的邻接列表开始。以下是上图的邻接列表：
graph = dict()
graph['A'] = ['B', 'S']
graph['B'] = ['A']
graph['S'] = ['A','G','C']
graph['D'] = ['C']
graph['G'] = ['S','F','H']
graph['H'] = ['G','E']
graph['E'] = ['C','H']
graph['F'] = ['C','G']
graph['C'] = ['D','S','E','F'] DFS 算法的实现首先创建一个列表来存储访问的节点。graph_stack栈变量用于帮助遍历过程。我们使用一个常规 Python 列表作为栈。名为root的起始节点与图的邻接矩阵 graph 一起传递。root被推送到栈上。node = root保存栈中的第一个节点：
def depth_first_search(graph, root):
visited_vertices = list()
graph_stack = list()
graph_stack.append(root)
node = root 如果栈不是空的，while循环的主体将被执行。如果node不在访问节点列表中，我们将其添加。node的所有相邻节点由adj_nodes = graph[node]采集。如果访问了所有相邻的节点，我们将从栈中弹出该节点，并将node设置为graph_stack[-1]。graph_stack[-1]是栈上的顶部节点。continue语句跳回while循环测试条件的开头。
while len(graph_stack) > 0:
if node not in visited_vertices:
visited_vertices.append(node)
adj_nodes = graph[node]
if set(adj_nodes).issubset(set(visited_vertices)):
graph_stack.pop()
if len(graph_stack) > 0:
node = graph_stack[-1]
continue
else:
remaining_elements =
set(adj_nodes).difference(set(visited_vertices))
first_adj_node = sorted(remaining_elements)[0]
graph_stack.append(first_adj_node)
node = first_adj_node
return visited_vertices 另一方面，如果未访问所有相邻节点，则通过使用remaining_elements = set(adj_nodes).difference(set(visited_vertices))语句查找adj_nodes和visited_vertices之间的差异来获得尚未访问的节点。
sorted(remaining_elements)中的第一项被分配给first_adj_node，并推送到栈上。然后，我们将栈顶部指向该节点。
当while循环存在时，我们将返回visited_vertices。
我们现在将通过前面的例子来解释源代码的工作原理。选择A节点作为我们的起始节点。将推到栈上并添加到visisted_vertices列表中。在这样做时，我们将其标记为已被访问。graph_stack栈是通过一个简单的 Python 列表实现的。我们的栈现在只有一个元素。我们检查了A节点的相邻节点、B和s。为了测试A的所有相邻节点是否都被访问过，我们使用if语句：
if set(adj_nodes).issubset(set(visited_vertices)):
graph_stack.pop()
if len(graph_stack) > 0:
node = graph_stack[-1]
continue 如果访问了所有节点，则弹出栈顶部。如果graph_stack栈不是空的，我们将栈顶部的节点分配给node，并开始while循环体的另一次执行。如果adj_nodes中的所有节点都是visited_vertices的子集，set(adj_nodes).issubset(set(visited_vertices))语句将计算为True。如果if语句失败，则表示仍有一些节点需要访问。我们通过remaining_elements = set(adj_nodes).difference(set(visited_vertices))获得该节点列表。
参照图，B和S节点将存储在remaining_elements中。我们将按字母顺序访问列表，如下所示：
first_adj_node = sorted(remaining_elements)[0]
graph_stack.append(first_adj_node)
node = first_adj_node我们对remaining_elements进行排序，并将第一个节点返回给first_adj_node。这将返回B。我们通过将B节点附加到graph_stack来将其推送到栈上。我们通过将B节点分配给node来准备访问。
在while循环的下一次迭代中，我们将B节点添加到visited nodes的列表中。我们发现B的唯一相邻节点A已经被访问。因为B的所有相邻节点都已被访问，所以我们将其从栈中弹出，留下A作为栈中的唯一元素。我们返回A并检查其相邻节点是否都已被访问。A节点现在有S作为唯一未访问的节点。我们将S推到栈中，然后重新开始整个过程。
遍历的输出为A-B-S-C-D-E-H-G-F。
DFS 在解决迷宫问题、查找连接组件和查找图的桥等方面都有应用。
我们经常需要使用图来查找两个节点之间的路径。有时，需要找到节点之间的所有路径，在某些情况下，我们可能需要找到节点之间的最短路径。例如，在路由应用中，我们通常使用各种算法来确定从源节点到目标节点的最短路径。对于未加权图，我们只需确定它们之间边数最少的路径。如果给定一个加权图，我们必须计算通过一组边的总权重
因此，在不同的情况下，我们可能需要使用不同的算法找到最长或最短的路径。
优先级队列是一种数据结构，类似于存储数据及其相关优先级的队列和栈数据结构。在优先级队列中，具有最高优先级的项目首先得到服务。优先级队列通常使用堆实现，因为它在这方面非常有效；但是，它可以使用其他数据结构实现。它是一个修改过的队列，以最高优先级的顺序返回项目，而队列以添加项目的顺序返回项目。优先级队列用于许多应用，如 CPU 调度。
让我们考虑一个例子来证明优先级队列在正则队列上的重要性。假设在商店中，客户排队时，服务只在队列的前面提供。每位顾客都会在排队等候一段时间后才能得到服务。如果队列中四个客户花费的时间单位分别为 4、30、2 和 1，则队列中花费的平均时间为(4 + 34 + 36 + 37)/4，即27.75。但是，如果我们将优先级条件与存储在队列中的数据相关联，那么我们可以为花费最少时间的客户提供更多优先级。在这种情况下，将按照客户花费的时间顺序为客户提供服务，即按照 1、2、4、30 的顺序。因此，平均等待时间为(1 + 3 + 7 + 37)/4，现在等于12——一个更好的平均等待时间。显然，以最少的时间为客户服务是有好处的。这种按优先级或其他标准选择下一项的方法是创建优先级队列的基础。优先级队列主要使用堆来实现
堆是满足堆属性的数据结构。heap 属性表示父节点与其子节点之间必须存在某种关系。此属性必须应用于整个堆。
在最小堆中，父级和子级之间的关系是父级的值必须始终小于或等于其子级。因此，堆中最低的元素必须是根节点。
另一方面，在最大堆中，父堆大于或等于其子堆。由此可知，最大值构成根节点。
堆是二叉树，虽然我们将使用二叉树，但实际上我们将使用一个列表来表示它。堆存储一个完整的二叉树。完整的二叉树是指在开始填充下一行之前，必须完全填充每一行，如下图所示：
为了简化索引的计算，我们将列表中的第一项（索引 0）留空。之后，我们将树节点从上到下、从左到右放入列表中，如下图所示：
如果仔细观察，您会发现您可以很容易地检索到n索引处任何节点的子节点。左侧子项位于2n，右侧子项位于2n + 1。这始终是正确的。例如，C 节点将位于3索引，因为C是a节点的右子节点，其索引为1，因此它将成为2n+1 = 2*1 + 1 = 3。
让我们讨论一下使用 Python 实现最小堆，因为一旦我们了解了最小堆，实现最大堆将更加简单。我们从 heap 类开始，如下所示：
class Heap:
def __init__(self):
self.heap = [0]
self.size = 0 我们用零来初始化堆列表，以表示伪第一个元素（请记住，我们这样做只是为了简化数学）。我们还创建一个变量来保存堆的大小。这样做是不必要的，因为我们可以检查列表的大小，但我们必须始终记住将其减少一。因此，我们选择保留一个单独的变量。
将项目插入最小堆分两步进行。首先，我们将新元素添加到列表的末尾（我们理解为树的底部），并将堆的大小增加 1。其次，在每次插入操作之后，我们需要在堆树中排列新元素，以满足堆属性的方式组织所有节点。这是为了提醒我们，min 堆中最低的元素必须是根元素
首先，我们创建一个帮助方法，称为 AuthT0}，它负责插入插入后的所有节点。我们考虑在 MIN 堆中添加元素的例子。我们在下图中提供了一个示例堆，希望在其中插入2的值：
新元素已占用第三行或第三层的最后一个插槽。其指标值为7。现在我们将该值与其父级进行比较。父项位于索引7/2 = 3（整数除法）。该元素包含6，因此我们交换2，如下所示：
我们的新元素已被交换并上移到3索引。我们还没有到达堆的顶部（3/2>0，所以我们继续。我们元素的新父元素位于索引3/2=1。因此，我们进行比较，必要时再次交换：
在最后一次交换之后，剩下的堆如下所示。请注意，它遵循堆的定义：
下面是我们在 min 堆中插入一个元素后的arrange()方法的实现：
def arrange(self, k): 我们将循环，直到到达根节点，这样我们就可以继续将元素按需要的高度排列。由于我们使用整数除法，一旦我们低于2，循环就会爆发：
while k // 2 > 0: 比较父对象和子对象。如果父项大于子项，则交换两个值：
if self.heap[k] < self.heap[k//2]:
self.heap[k], self.heap[k//2] = self.heap[k//2],
self.heap[k] 最后，让我们不要忘记向上移动树：
k //= 2 此方法确保元素的顺序正确。
现在，我们只需要从insert方法调用它：
def insert(self, item):
self.heap.append(item)
self.size += 1
self.arrange(self.size) 注意，insert中的最后一行调用arrange()方法，根据需要重新组织堆。
pop操作从堆中删除一个元素。从最小堆中删除元素的原因是，首先要找出要删除的项的索引，然后组织堆，使其满足 heap 属性。但是，更常见的是从 min heap 弹出最小值，根据 min heap 的属性，我们可以通过其根值获得最小值。因此，为了从 min 堆中获取并移除最小值，我们移除根节点并重新组织堆中的所有节点。我们还将堆的大小减小 1。
但是，一旦根被弹出，我们就需要一个新的根节点。为此，我们只需从列表中选取最后一项，并将其作为新根。也就是说，我们把它移到列表的开头。但是，选定的最后一个节点可能不是堆的最低元素，因此我们必须重新组织堆的节点。为了根据 min-heap 属性构造所有节点，我们采用了一种与在堆中插入元素时使用的arrange()方法相反的策略。我们将最后一个节点设为新根节点，然后根据需要让它向下移动（或下沉）。
让我们考虑一个例子来帮助理解下面的堆中的这个概念。首先，我们弹出root元素：
如果我们选择向上移动根的一个子树，我们将必须找出如何重新平衡整个树结构，这将更加复杂。因此，我们做了一些非常有趣的事情。我们向上移动列表中最后一个元素，以填充root元素的位置；例如，在下面的堆示例中，最后一个元素6被放置在根位置：
现在，这个元素显然不是堆中最低的。所以，我们必须把它扔到垃圾堆里。首先，我们需要决定是把它放向左边还是右边的孩子。我们比较这两个子元素，这样最低的元素就是根下沉时向上移动的元素。在本例中，我们比较根的两个子项，即5和3：
右边的子项明显更小：其索引为3，表示根索引2+1*。我们继续将新的根节点与该索引处的值进行比较，如下所示：
现在我们的节点已经下移到索引3。我们需要将它与它的孩子中较小的孩子进行比较。但是，现在我们只有一个子级，所以我们不需要担心与哪个子级进行比较（对于最小堆，它总是较小的子级）：
这里没有必要交换。因为没有更多的行了，所以我们不需要做任何其他事情。请注意，在sink()操作完成后，堆符合我们对堆的定义。
现在我们可以开始实施这一点了。但是在我们实现sink()方法之前，我们需要注意如何确定哪些子节点要与父节点进行比较。让我们把这个选择放在它自己的小方法中，只是为了让代码看起来更简单一些：
def minindex(self, k): 我们可能会超出列表的末尾，如果我们这样做，那么我们将返回左边子级的索引：
if k * 2 + 1 > self.size:
return k * 2 否则，我们只返回两个孩子中较小者的索引：
elif self.heap[k*2] < self.heap[k*2+1]:
return k * 2
else:
return k * 2 + 1现在我们可以创建sink函数。正如我们之前所做的那样，我们将循环，以便我们可以根据需要将元素下沉：
def sink(self, k):
while k*2 <- self.size: 接下来，我们需要知道哪些是左派儿童，哪些是右派儿童。这就是我们使用minindex()功能的地方：
mi = self.minindex(k)正如我们在插入操作期间在arrange()方法中所做的那样，我们比较父级和子级以确定是否需要进行交换：
if self.heap[k] > self.heap[mi]:
self.heap[k], self.heap[mi] = self.heap[mi],
self.heap[k] 我们需要确保沿着树向下移动，这样我们就不会陷入循环中，如下所示：
k = mi 现在唯一剩下的就是实现主方法本身。这非常简单，因为咕噜工作是通过sink()方法执行的：
def pop(self):
item = self.heap[1]
self.heap[1] = self.heap[self.size]
self.size -= 1
self.heap.pop()
self.sink(1)
return item现在，让我们测试堆的实现，并用一个例子来讨论这个问题。我们首先通过逐个插入 10 个元素来构建堆。让元素为{4, 8, 7, 2, 9, 10, 5, 1, 3, 6}。首先，我们用这些元素手动创建一个堆，然后我们将实现它并验证我们是否正确地执行了它：
在上图中，我们展示了在堆中插入元素的逐步过程。在这里，我们继续添加元素，如图所示：
最后，我们向堆中插入一个元素6：
现在，让我们首先创建堆并插入该数据，如以下代码所示：
h = Heap()
for i in (4, 8, 7, 2, 9, 10, 5, 1, 3, 6):
h.insert(i) 我们可以打印堆列表，只是为了检查元素的顺序。如果将其重新绘制为树结构，您会注意到它满足堆的必需属性，类似于我们手动创建的：
print(h.heap) 现在，我们将弹出项目，一次一个。注意这些项目是如何按照从低到高的顺序排列的。另外，请注意堆列表在每次pop之后是如何变化的。sink()方法将重新组织堆中的所有项：
for i in range(10):
n = h.pop()
print(n)
print(h.heap) 在前一节中，我们已经讨论了使用最小堆的相关概念，因此通过简单地反转逻辑来实现最大堆应该是一项简单的任务。
我们将使用我们在第 10 章、排序中再次讨论的关于排序算法的最小堆，并将重写用于对列表中的元素进行排序的代码。这些算法称为堆排序算法。
选择算法属于一类算法，旨在解决在列表中查找i<sup>th</sup>最小元素的问题。当列表按升序排序时，列表中的第一个元素将是列表中最小的项。列表中的第二个元素将是列表中第二小的元素。列表中的最后一个元素将是列表中最小（或最大）的元素。
在创建堆数据结构时，我们已经了解到对pop方法的调用将返回最小堆中的最小元素。从最小堆弹出的第一个元素是列表中最小的元素。类似地，从最小堆弹出的第七个元素将是列表中第七小的元素。因此，要找到列表中最小的元素i<sup>th</sup>，我们需要多次弹出 heap i。这是一种非常简单有效的方法，可以找到列表中最小的元素i<sup>th</sup>。
然而，在第 11 章、选择算法中，我们将研究更多的方法来找到i<sup>th</sup>——列表中的最小元素。
选择算法可用于过滤噪声数据，查找列表中的中值、最小值和最大值元素，甚至可用于计算机象棋程序。
本章讨论了图和堆。图的主题对于许多现实世界的应用来说非常重要和有用。我们已经研究了使用列表和字典在 Python 中表示图的不同方法。为了遍历图，我们使用了两种方法：BFS 和 DFS。
然后，我们将注意力转移到堆和优先级队列上，以了解它们的实现。本章最后讨论了如何使用堆的概念来查找列表中最小的元素i<sup>th</sup>。
下一章将引导我们进入搜索领域，以及我们可以有效搜索列表中项目的各种方法。**