[python] 堆
在Python中，堆（Heap）的实现主要通过标准库中的 heapq 模块来完成。以下是关于 heapq 模块的关键信息总结：
- 基本功能
heapq提供了堆队列算法的实现，默认实现的是最小堆（即堆顶元素始终是最小值。- 核心操作包括：
-
heapify(iterable)：将列表转换为堆结构，时间复杂度为 O(n)。
-
heappush(heap, item)：插入元素并维护堆性质，时间复杂度为 O(log n)。
-
heappop(heap)：弹出最小元素并调整堆，时间复杂度为 O(log n)。
-
heapreplace(heap, item)：弹出最小元素后插入新元素，效率高于分开操作。
-
nsmallest(n, iterable)和nlargest(n, iterable)：快速获取前 N 个最小或最大值。
- 底层实现
heapq使用列表（List）作为底层存储结构，通过完全二叉树的索引规则（父节点索引为i//2，子节点为2*i和2*i+1）维护堆性质。- 堆的物理存储是列表，但逻辑上需满足堆属性（父节点值 ≤ 子节点值）。
- 应用场景
- 优先级队列：通过元组
(priority, item)实现，按优先级处理任务。 - 堆排序：通过反复调用
heappop实现 O(n log n) 的排序。 - 图算法：如 Dijkstra 最短路径算法或 Prim 最小生成树算法。
- 大数据处理：高效获取数据流中的前 K 个极值。
- 高级技巧
- 实现最大堆：通过对元素取负数（如
-x）模拟最大堆。 - 合并堆：使用
merge函数合并多个有序堆。
示例代码
import heapq # 创建最小堆
heap = [3, 1, 4, 1, 5]
heapq.heapify(heap) # 输出: 1, 1, 4, 3, 5 # 插入和弹出
heapq.heappush(heap, 2) # 堆变为 1, 1, 4, 3, 5, 2
min_val = heapq.heappop(heap) # 返回 1，堆变为 1, 2, 4, 3, 5 # 实现最大堆
max_heap = []
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -3)
# 弹出最大值
max_value = -heapq.heappop(max_heap)
print(max_value) # 输出: 5# 寻找前 K 个最大/最小值
numbers = [4, 1, 7, 3, 8, 5]
smallest = heapq.nsmallest(3, numbers)
largest = heapq.nlargest(2, numbers)
print(smallest) # 输出: [1, 3, 4]
print(largest) # 输出: [8, 7]# 优先级队列示例
tasks = []
heapq.heappush(tasks, (2, "Task A"))
heapq.heappush(tasks, (1, "Task B"))
heapq.heappush(tasks, (3, "Task C"))
while tasks: priority, task = heapq.heappop(tasks) print(f"Executing {task} with priority {priority}")# 按元组第一个元素排序
# 输出：
# Executing Task B with priority 1
# Executing Task A with priority 2
# Executing Task C with priority 3