目录
1. 堆的基本概念
2. heapq模块介绍
3. 基本操作
创建堆
插入元素
弹出最小元素
替换元素
合并堆
其他辅助函数
4. 高级用法
堆排序
优先级队列
最小堆和最大堆
5. 实际应用场景
Dijkstra算法
K路归并
频次统计
6. 性能分析
7. 总结
1. 堆的基本概念
堆是一种特殊的树形数据结构，满足以下性质：
- 堆总是完全二叉树（Complete Binary Tree）。
- 堆中的每个节点都满足堆性质（Heap Property），即每个节点的值总是不大于（或不小于）其子节点的值。前者称为最小堆（Min Heap），后者称为最大堆（Max Heap）。
在最小堆中，根节点包含最小值，而在最大堆中，根节点包含最大值。堆常用于实现优先级队列以及一些排序算法，如堆排序。
2. heapq模块介绍
Python的heapq模块提供了一组函数用于操作堆，其中所有函数都基于列表实现。通过heapq，你可以将列表当作堆来使用，而不是重新实现堆的数据结构。
3. 基本操作
创建堆
在heapq中，没有专门的堆数据结构，任何列表都可以被视为堆。通过heapq.heapify函数，可以将一个无序列表转换为堆。
import heapq# 创建一个列表
data = [3, 1, 4, 1, 5, 9, 2, 6, 5]# 将列表转换为堆
heapq.heapify(data)print("Heapified list:", data) # 输出: [1, 1, 2, 3, 5, 9, 4, 6, 5]
插入元素
使用heapq.heappush函数可以将一个新元素插入到堆中，同时保持堆的性质。
heapq.heappush(data, 7)
print("After push:", data) # 输出: [1, 1, 2, 3, 5, 9, 4, 6, 5, 7]
弹出最小元素
使用heapq.heappop函数可以弹出并返回堆中的最小元素，同时保持堆的性质。
min_elem = heapq.heappop(data)
print("Popped element:", min_elem) # 输出: 1
print("After pop:", data) # 输出: [1, 3, 2, 5, 5, 9, 4, 6, 7]
替换元素
使用heapq.heapreplace函数可以弹出堆中的最小元素，并将一个新元素插入到堆中。这是一个原子操作，比先调用heappop再调用heappush效率更高。
heapq.heapreplace(data, 8)
print("After replace:", data) # 输出: [2, 3, 4, 5, 5, 9, 8, 6, 7]
合并堆
使用heapq