python中的堆heapq

1.什么是堆？

堆是一种非线性数据结构，其中二叉堆是一颗完全二叉树，可以用数组实现。大顶堆每个节点的值都不小于它的孩子节点的值。小顶堆则相反。

完全二叉树 - wulongming88 - 博客园

2.python中的标准库模块heapq

1）创建堆

①使用空列表初始化堆，并使用heapq.heappush向堆添加元素

import heapq
heap = []
heapq.heappush(heap, 0) 

②使用heapify将列表转化为堆

elements = [0]
heapq.heapify(elements)

 2）弹出堆顶值

heapq.heappop(heap)

3）获取堆中最小的N个值或最大的N个值

heapq.nsmallest(N, heap), heapq.nlargest(N, heap)

其他函数见参考资料。

3.参考资料

heapq --- 堆队列算法 — Python 3.10.2 文档