堆是一个二叉树，其中每个父节点的值都小于或等于其所有子节点的值。
整个堆的最小元素总是位于二叉树的根节点。
python的heapq模块提供了对堆的支持。
堆数据结构最重要的特征是heap[0]永远是最小的元素
代码示例
import heapq
# 添加元素，容器是list列表，元素存放顺序是小根堆的顺序
h = []
heapq.heappush(h, 2)
heapq.heappush(h, 3)
h
Out[6]:
[2, 3]
# 列表转换为堆
lst = [2, 3, 4, 6, 9, 1, 5]
heapq.heapify(lst)
lst
Out[9]:
[1, 3, 2, 6, 9, 4, 5]
# 弹出最小值
heapq.heappop(lst)
Out[10]:
1
lst
Out[11]:
[2, 3, 4, 6, 9, 5]
# 弹出最小值，添加新元素
heapq.heapreplace(lst, 8)
Out[14]:
2
lst
Out[15]:
[3, 6, 4, 8, 9, 5]
# 和根元素比较，如果比其大则替换
heapq.heappushpop(lst, 4)
Out[16]:
3
lst
Out[17]:
[4, 6, 4, 8, 9, 5]
# 和根元素比较，如果比其小则不替换
heapq.heappushpop(lst, 3)
Out[18]:
3
lst
Out[19]:
[4, 6, 4, 8, 9, 5]
# 合并堆
h = [10, 11, 13]
l = heapq.merge(lst, h)
list(l)
Out[25]:
[4, 6, 4, 8, 9, 5, 10, 11, 13]
# 查询最大的n个元素
heapq.nlargest(3, lst)
Out[26]:
[9, 8, 6]
# 查询最小的n个元素
heapq.nsmallest(3, lst)
Out[27]:
[4, 4, 5]
参考
