数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学Python中的堆队列（或heapq）
堆队列是一种特殊的树形结构，其中每个父节点都小于或等于其子节点。在Python中，它是使用heapq模块实现的。它在实现优先队列方面非常有用，在优先队列中，权重较高的队列项在处理中具有更高的优先级。
创建堆
堆队列是使用Python的内置库heapq创建的。这个库包含执行堆数据结构上各种操作的相关函数。以下是这些函数的列表。
- heapify – 此函数将普通列表转换为堆。在生成的堆中，最小元素被推送到索引位置0。但其余的数据元素不一定已排序。
- heappush – 此函数将元素添加到堆中，而不会更改当前堆。
- heappop – 此函数返回堆中最小的数据元素。
- heapreplace – 此函数用函数中提供的新值替换最小的数据元素。
创建堆
堆的创建只需使用包含heapify函数的元素列表即可。在下面的示例中，我们提供一个元素列表，heapify函数会重新排列这些元素，并将最小元素放到第一个位置。
示例
import heapq H = [21,1,45,78,3,5] # Use heapify to rearrange the elements heapq.heapify(H) print(H)
输出
执行上述代码时，会产生以下结果：
[1, 3, 5, 78, 21, 45]
插入堆中
将数据元素插入堆中总是将元素添加到最后一个索引。但是，只有当新添加的元素值最小时，才能再次应用heapify函数将其带到第一个索引。在下面的示例中，我们插入数字8。
示例
import heapq H = [21,1,45,78,3,5] # Covert to a heap heapq.heapify(H) print(H) # Add element heapq.heappush(H,8) print(H)
输出
执行上述代码时，会产生以下结果：
[1, 3, 5, 78, 21, 45] [1, 3, 5, 78, 21, 45, 8]
从堆中移除
可以使用此函数移除第一个索引处的元素。在下面的示例中，该函数将始终移除索引位置1处的元素。
示例
import heapq H = [21,1,45,78,3,5] # Create the heap heapq.heapify(H) print(H) # Remove element from the heap heapq.heappop(H) print(H)
输出
执行上述代码时，会产生以下结果：
[1, 3, 5, 78, 21, 45] [3, 21, 5, 78, 45]
替换堆中的元素
heapreplace函数总是移除堆中最小的元素，并将新的传入元素插入到某个位置，该位置不受任何顺序的限制。
示例
import heapq H = [21,1,45,78,3,5] # Create the heap heapq.heapify(H) print(H) # Replace an element heapq.heapreplace(H,6) print(H)
输出
执行上述代码时，会产生以下结果：
[1, 3, 5, 78, 21, 45] [3, 6, 5, 78, 21, 45]
更新于：2020年6月9日
5K+ 次查看
广告