堆数据结构(heapq)简单应用

## 堆数据结构(heapq)简单应用
 1 # 堆数据结构 heapq
 2 # 常用方法：nlargest(),nsmallest(),heapify(),heappop()
 3 # 如果需要的个数较小，使用nlargest或者nsmallest比较好
 4 # 如果需要的个数已经接近了序列长度，使用sorted()[:N]获取前N个数据比较好
 5 # 如果只需要唯一一个最大或最小值，则直接使用max()或者min()
 6 
 7 import heapq
 8 
 9 
10 nums = [1,3,5,67,7,34,6,8,5,-12,-45,-234,232]
11 print(heapq.nlargest(3, nums))
12 # [232, 67, 34]
13 print(heapq.nsmallest(3, nums))
14 # [-234, -45, -12]
15 
16 words = ['happy', 'sad', 'fun', 'sweet', 'blue']
17 print(heapq.nlargest(3, words))
18 # ['sweet', 'sad', 'happy']
19 print(heapq.nsmallest(3, words))
20 # ['blue', 'fun', 'happy']
21 
22 print(heapq.nsmallest(3, 'qazwsxedcvbnm'))
23 # ['a', 'b', 'c']
24 
25 t = (1,2,3,4)
26 print(heapq.nlargest(2, t))
27 #[4, 3]
28 
29 students = [
30     {"name": "Stanley", "score": 94},
31     {"name": "Lily", "score": 98},
32     {"name": "Bob", "score": 87},
33     {"name": "Well", "score": 85}
34 ]
35 
36 print(heapq.nlargest(len(students), students, key=lambda s: s["score"])) # 需要个数为序列长度，不好
37 """
38 [{'name': 'Lily', 'score': 98},
39 {'name': 'Stanley', 'score': 94},
40 {'name': 'Bob', 'score': 87},
41 {'name': 'Well', 'score': 85}]
42 """
43 
44 print(sorted(students, key=lambda s: s['score'], reverse=True))  # 好
45 """
46 [{'name': 'Lily', 'score': 98},
47 {'name': 'Stanley', 'score': 94},
48 {'name': 'Bob', 'score': 87},
49 {'name': 'Well', 'score': 85}]
50 """
51 
52 nums = [1,3,5,67,7,34,6,8,5,-12,-45,-234,232]
53 heapq.heapify(nums)
54 print(nums)
55 # [-234, -45, 1, 5, -12, 5, 6, 8, 67, 3, 7, 34, 232]
56 print(heapq.heappop(nums))  # heappop 返回的是序列中的第一个元素，也就是最小的一个元素
57 # -234
58 
59 
60 # 使用heapq编写优先级队列
61 import heapq
62 
63 
64 class PriorityQueue(object):
65     def __init__(self):
66         self._queue = []
67         self._index = 0
68 
69     def push(self, item, priority):
70         heapq.heappush(self._queue, (-priority, self._index, item))
71         # 第一个参数是添加进的目标序列，
72         # 第二个参数是将一个元组作为整体添加进序列，目的是为了方便比较，
73         # 在priority相等的情况下，比较_index
74         # priority为负数使得添加时按照优先级从大到小排序，因为堆排序的序列的第一个元素永远是最小的
75         self._index += 1
76 
77     def pop(self):
78         # 返回按照-priority 和 _index 排序后的第一个元素(是一个元组)的最后一个元素(item)
79         return heapq.heappop(self._queue)[-1]
80 
81 q = PriorityQueue()
82 q.push("bar", 2)
83 q.push("foo", 1)
84 q.push("gork", 3)
85 q.push("new", 1)
86 
87 print(q.pop())
88 print(q.pop())
89 print(q.pop())
90 print(q.pop())
91 """
92 gork  # 优先级最高
93 bar   # 优先级第二
94 foo   # 优先级与new相同，比较index，因为先加入，index比new小，所以排在前面
95 new
96 """
参考资料：
　　Python Cookbook, 3rd edition, by David Beazley and Brian K. Jones (O’Reilly).