堆是一个二叉树，其中每个父节点的值都小于或等于其所有子节点的值。
整个堆的最小元素总是位于二叉树的根节点。
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]
参考
