cookbook 1.5

大马强

实现优先级队列

问题描述：
        希望给定一个可以设置优先级排序的序列，pop的顺序优先返回优先级最高的元素

借助heapq库实现

1. class priorityqueue():
   
2.     def __init__(self) -> None:
   
3.         self._queue = []
   
4.         self._index = 0
   
5. 
   
6.     def push(self, item, prority):
   
7.         heapq.heappush(self._queue, (-prority, self._index, item))  # -prority heapq中数值越小优先级越高，类似堆
   
8.         self._index += 1
   
9. 
   
10.     def pop(self):
    
11.         return heapq.heappop(self._queue)[-1]
    
12. 
    
13. 
    
14. class Item():
    
15.     def __init__(self, name) -> None:
    
16.         self.name = name
    
17. 
    
18.     def __repr__(self) -> str:
    
19.         return "Item({!r})".format(self.name)
    
20. 
    
21. 
    
22. q = priorityqueue()
    
23. q.push(Item("foo"), 1)
    
24. q.push(Item("coo"), 4)
    
25. q.push(Item("voo"), 5)
    
26. q.push(Item("boo"), 1)
    
27. q.push(Item("noo"), 3)

复制代码

(-5, 2, Item('voo'))
(-4, 1, Item('coo'))
(-3, 4, Item('noo'))
(-1, 0, Item('foo'))
(-1, 3, Item('boo'))

• 比较的原理是相应下标依次对比，先比tuple[0] tuple[1]...., []和{}比较原理一样
• 同优先级按照其push顺序来排序
• 三元元组形式是为了进行方便的比较