python 堆的使用 heapq_heapq 包

相关文章： heapq文档

堆，对于python来说就是一个按照特殊顺序排列的列表，在python中有专门的包heapq来实现关于堆的一系列操作，堆最重要的性质就是它的第一个元素一直是整个列表中最大/最小的那个，比不停的使用min要快得多

python中的堆默认是小根堆，也就是所有的父节点的值都小于它的子节点，实际上的实现就是第i个元素的值要小于第2i+1和第2i+2个

如何使用

首先，如何构造一个堆
堆，就是一个列表，所以你得有一个待构造成堆的列表也就是一连串的数据：

import heapq
# 如何构造一个小根堆
# 初始化一个堆，默认是小根堆，其实就是新建一个列表然后使用heapq.heapify
h = [1, 9, 8, 7, 4, 5]
# 使用heapify可以直接将一个乱的列表转换成小根堆
heapq.heapify(h)
print(h)  # [1, 4, 5, 7, 9, 8],注意heapify之后不是递增排序，是个小根堆，时间复杂度O(n)

1
2
3
4
5
6
7
8

当然，也可以先创建一个空列表然后一个一个添加数，它会自动构造小根堆

h = []
for i in [1, 9, 8, 7, 4, 5]:
# 使用heappush()一个个的添加
    heapq.heappush(h, i)
print(h)
1
2
3
4
5

其他常用的操作
弹出第一个元素，也就是弹出最小的元素并将保持小根堆

min_num = heapq.heappop(h)
1

填入一个元素并小根堆化之后再弹出最小的那个元素并将剩余的元素小根堆化

min_num = heapq.heappushpop(h,item)
1

先弹出最小的元素再填入一个元素

min_num = heapq.heapreplace(heap, item)
1

关于堆的例题：
H2402