Python中的heapq

1.基本介绍

堆是非线性的树形的数据结构，有两种堆，大根堆与小根堆。

• 大根堆：树中各个父节点的值总是大于或等于任何一个子节点的值。
• 小根堆：树中各个父节点的值总是小于或等于任何一个子节点的值。

我们一般使用二叉堆来实现优先级队列，它的内部调整算法复杂度为 logN。堆是一个二叉树，其中小根堆每个父节点的值都小于或等于其所有子节点的值。整个小根堆的最小元素总是位于二叉树的根节点。

python 的 heapq 模块提供了对堆的支持，heapq 堆数据结构最重要的特征是 heap[0] 永远是最小的元素。heapq库中的堆默认是小根堆。

import heapq
1

👇 增加元素，heap为定义堆，item为增加的元素。

heapq.heappush(heap, item) 
1

👇 将列表转换为堆

heapq.heapify(list)
1

👇 删除并返回最小值，因为堆的特征是 heap[0] 永远是最小的元素，所以一般都是删除第一个元素。

heapq.heappop(heap)
1

👇 先将堆顶的数据出堆，然后将 item 添加到堆中。

heapq.heapreplace(heap.item)
1

👇 先将 item 添加到堆中，然后将堆顶的数据出堆。

heapq.heappushpop(list, item)
1

👇 将多个堆合并。

heapq.merge(a1, a2, …)
1

👇 查询堆中最大的n个元素。

heapq.nlargest(n, heap_name)
1

👇 查询堆中最小的n个元素。

heapq.nsmallest(n, heap_name)
1

如果需要的个数较小，使用 nlargest 或者 nsmallest 比较好；
如果需要的个数已经接近了序列长度，使用 sorted()[:N] 获取前 N 个数据比较好；
如果只需要唯一的一个最大或最小值，则直接使用 max() 或者 min()。

2.常用代码

2.1 创建堆

# 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)
1
2
3
4
5
6
7
8
9
10
11
12

结果如下

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]
1
2
3

• heappush(heap, num)，先创建一个空堆，然后将数据一个一个地添加到堆中。每添加一个数据后，heap 都满足小顶堆的特性。
• heapify(array)，直接将数据列表调整成一个小顶堆。

2.2 使用heapq实现堆排序

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)
1
2
3
4
5
6
7

结果如下

5
heap sort result:  [5, 7, 10, 15, 17, 21, 24, 27, 30, 36, 45, 50]
1
2