Python编程：heapq模块堆排序

堆是一个二叉树，其中每个父节点的值都小于或等于其所有子节点的值。
整个堆的最小元素总是位于二叉树的根节点。
python的heapq模块提供了对堆的支持。
堆数据结构最重要的特征是heap[0]永远是最小的元素

代码示例

import heapq

# 添加元素，容器是list列表，元素存放顺序是小根堆的顺序
h = []
heapq.heappush(h, 2)
heapq.heappush(h, 3)

h
Out[6]: 
[2, 3]


# 列表转换为堆
lst = [2, 3, 4, 6, 9, 1, 5]
heapq.heapify(lst)
lst
Out[9]: 
[1, 3, 2, 6, 9, 4, 5]


# 弹出最小值
heapq.heappop(lst)
Out[10]: 
1

lst
Out[11]: 
[2, 3, 4, 6, 9, 5]


# 弹出最小值，添加新元素
heapq.heapreplace(lst, 8)
Out[14]: 
2
lst
Out[15]: 
[3, 6, 4, 8, 9, 5]


# 和根元素比较，如果比其大则替换
heapq.heappushpop(lst, 4)
Out[16]: 
3
lst
Out[17]: 
[4, 6, 4, 8, 9, 5]

# 和根元素比较，如果比其小则不替换
heapq.heappushpop(lst, 3)
Out[18]: 
3
lst
Out[19]: 
[4, 6, 4, 8, 9, 5]


# 合并堆
h = [10, 11, 13]
l = heapq.merge(lst, h)
list(l)
Out[25]: 
[4, 6, 4, 8, 9, 5, 10, 11, 13]

# 查询最大的n个元素
heapq.nlargest(3, lst)
Out[26]: 
[9, 8, 6]

# 查询最小的n个元素
heapq.nsmallest(3, lst)
Out[27]: 
[4, 4, 5]


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
 

参考

1. python3入门之堆（heapq）
2. Python标准库模块之heapq

文章来源: pengshiyu.blog.csdn.net，作者：彭世瑜，版权归原作者所有，如需转载，请联系作者。

原文链接：pengshiyu.blog.csdn.net/article/details/90229831