heapq
时间: 2023-07-26 18:24:13 浏览: 48
`heapq` 是 Python 中的一个模块,提供了堆(heap)操作的函数。堆是一种特殊的树形数据结构,满足以下两个条件:
1. 堆是一个完全二叉树。
2. 堆中的每个节点的值都不大于(或不小于)其子节点的值。
Python 提供的 `heapq` 模块可以让我们轻松地实现堆的操作,包括:
- `heappush(heap, item)`:将元素 `item` 加入到堆 `heap` 中。
- `heappop(heap)`:弹出并返回堆 `heap` 中的最小元素。
- `heapify(x)`:将列表 `x` 转换为堆。
- `heapreplace(heap, item)`:弹出并返回堆 `heap` 中的最小元素,同时将元素 `item` 加入到堆中。
- `nlargest(k, iterable[, key])` 和 `nsmallest(k, iterable[, key])`:返回可迭代对象中最大或最小的 `k` 个元素。
例如,下面的代码演示了如何使用 `heapq` 来实现堆排序:
```python
import heapq
def heap_sort(arr):
h = []
for val in arr:
heapq.heappush(h, val)
return [heapq.heappop(h) for _ in range(len(h))]
arr = [4, 1, 3, 2, 5]
sorted_arr = heap_sort(arr)
print(sorted_arr) # 输出 [1, 2, 3, 4, 5]
```
在这个例子中,我们使用 `heappush` 将列表中的元素加入到堆中,然后使用 `heappop` 逐个弹出最小值,从而实现了堆排序。