一、heapq内置模块
Python中的heapq模块提供了一种堆队列heapq类型,这样实现堆排序等算法便相当方便,heapq 模块实现了适用于Python列表的最小堆排序算法。
堆是一个树状的数据结构,其中的子节点都与父母排序顺序关系。因为堆排序中的树是满二叉树,因此可以用列表来表示树的结构,即是对于从零开始的索引。
二、heapq 模块的使用
1.创建堆方法
创建堆的方法:
一种是使用一个空列表,然后使用heapq.heappush()函数把值加入堆中,另外一种就是使用heap.heapify(list)转换列表成为堆结构。
1、 heapq.heappush(heap, num) # 加入堆
2、heapq.heapify(list)
代码如下(示例):
import heapq
# 第一种
list= [4, 3, 8, 10, 54,99, 137]
heap = []
for i in list:
heapq.heappush(heap, i) # 加入堆
print([heapq.heappop(heap) for i in range(len(list))])
#[3, 4, 8, 10, 54, 99, 137]
# 第二种
list= [1, 8, 55, 19, 54, 2, 100]
heapq.heapify(list)
print([heapq.heappop(list) for i in range(len(list))])
#[1, 2, 8, 19, 54, 55, 100]
2.访问堆的方法
可以通过`heapq.heappop() 函数弹出堆中最小值
代码如下(示例):
list = [1, 8, 55, 19, 54, 2, 100]
heapq.heapify(list)
print(heapq.heappop(list))
2.获取堆的最大值、最小值方法
可以使用heapq.nlargest() 或heapq.nsmallest() 函数
代码如下(示例):
import heapq
list = [6, 3, 4, 2, 9]
print(heapq.nlargest(2, list))
print(heapq.nsmallest(4, list))
总结
常用方法:
- heapq.heappush(heap, item) heap为定义的堆,item增加的元素
- heapq.heapify(list) 将列表转换为堆
- heapq.heappop(heap) 删除并返回最小值,因为堆的特征是heap[0]永远是最小的元素,一般删除第一个元素
- heapq.nlargest(n,heap) 查询堆中的最大n个元素
- heapq.nsmallest(n,heap) 查询堆中的最小n个元素
说明:
需要取出的个数较小,使用nlargest或者nsmallest
需要取出的个数已经接近了序列长度,使用sorted()获取前n个
只需要唯一一个最大或最小值,直接使用max()、min()