堆是非线性的树形的数据结构，有两种堆，大根堆与小根堆。
- 大根堆：树中各个父节点的值总是大于或等于任何一个子节点的值。
- 小根堆：树中各个父节点的值总是小于或等于任何一个子节点的值。
我们一般使用二叉堆来实现优先级队列，它的内部调整算法复杂度为 logN。堆是一个二叉树，其中小根堆每个父节点的值都小于或等于其所有子节点的值。整个小根堆的最小元素总是位于二叉树的根节点。
python 的 heapq 模块提供了对堆的支持，heapq 堆数据结构最重要的特征是 heap[0] 永远是最小的元素。heapq库中的堆默认是小根堆。
import heapq
增加元素，heap为定义堆，item为增加的元素。
heapq.heappush(heap, item)
将列表转换为堆
heapq.heapify(list)
删除并返回最小值，因为堆的特征是 heap[0] 永远是最小的元素，所以一般都是删除第一个元素。
heapq.heappop(heap)
先将堆顶的数据出堆，然后将 item 添加到堆中。
heapq.heapreplace(heap.item)
先将 item 添加到堆中，然后将堆顶的数据出堆。
heapq.heappushpop(list, item)
将多个堆合并。
heapq.merge(a1, a2, …)
查询堆中最大的n个元素。
heapq.nlargest(n, heap_name)
查询堆中最小的n个元素。
heapq.nsmallest(n, heap_name)
如果需要的个数较小，使用 nlargest 或者 nsmallest 比较好；
如果需要的个数已经接近了序列长度，使用 sorted()[:N] 获取前 N 个数据比较好；
如果只需要唯一的一个最大或最小值，则直接使用 max() 或者 min()。
# coding=utf-8
import heapq
array = [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
heap = []
for num in array:
heapq.heappush(heap, num)
print("array:", array)
print("heap: ", heap)
heapq.heapify(array)
print("array:", array)
结果如下
array: [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21] heap: [5, 7, 21, 15, 10, 24, 27, 45, 17, 30, 36, 50] array: [5, 7, 21, 10, 17, 24, 27, 45, 15, 30, 36, 50]
- heappush(heap, num)，先创建一个空堆，然后将数据一个一个地添加到堆中。每添加一个数据后，heap 都满足小顶堆的特性。
- heapify(array)，直接将数据列表调整成一个小顶堆。
array = [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
heap = []
for num in array:
heapq.heappush(heap, num)
print(heap[0])
heap_sort = [heapq.heappop(heap) for _ in range(len(heap))]
print("heap sort result: ", heap_sort)
结果如下
5 heap sort result: [5, 7, 10, 15, 17, 21, 24, 27, 30, 36, 45, 50]
