實作優先級隊列（PythonCookbook1.5）

問題：

通過給定優先級對元素排序，且每次pop傳回優先級最高的那個元素

解決方案：

#原始形式 heappush(堆，項目)；heappop（項目）
import heapq
class PriorityQueue:
     def __init__(self):
         self.queue=[] #排序list
         self.index=[] #計數器，用于當優先級相同的情況
     def push(self,item,priority): #輸入item和優先級
         heapq.heappush(self.queue,(-priority,self.index,item)) #先比priority，比不出再比技術（早的先pop出）
         self.index += 1
     def pop(self):
         return heapq.heappop(self.queue)[-1] #pop出最後一個
         
#使用這個類
class Item:
    def __init__(self,name):
        self.name = name
    def __repr__(self):
        return 'Item({!r})'.format(self.name)
        #str.format()格式化字元串；return self.name但是以特定格式
        #!r -> repr() -> 将對象轉化為用解讀器讀取的形式；傳回一個對象的 string 格式


           

Point

1. heappop()傳回最小值，這裡題目要求傳回優先級最高，是以priority前加‘-’
2. push和pop操作的複雜度都是log，N很大的時候效率也很高
3. {}.format()是格式函數