>[success] # 一些常用的heapq熟悉 >[danger] ##### heapify -- 將列表轉換成堆 堆的重要特性就是第0個元素總是最小 ~~~ import heapq nums = [23,3,5,6,7,-1,5,6,1,10] # 為了不破壞原來的list集合所以特意重新轉換一下 heap = list(nums) heapq.heapify(heap) print(heap) 打印結果： [-1, 1, 5, 3, 7, 5, 23, 6, 6, 10] ~~~ >[danger] ##### heappop -- 刪除最小值 這個 運行速度O（logN）也就是堆越大，使用此方法的運行速度越慢 ~~~ import heapq nums = [23,3,5,6,7,-1,5,6,1,10] heap = list(nums) # 先轉換成堆然后再刪除 heapq.heapify(heap) # 刪除第0個元素 print(heapq.heappop(heap)) 打印結果： -1 ~~~ >[danger] ##### heapreplace -- 彈出最小值，然后將新參數加入 只彈出未添加時最小值，下面的例子當加入的是-3，彈出的是-1 ~~~ import heapq nums = [23,3,5,6,7,-1,5,6,1,10] heap = list(nums) # 先轉換成堆然后再刪除 heapq.heapify(heap) heapq.heapreplace(heap,66) print(heap) 打印結果： [1, 3, 5, 6, 7, 5, 23, 6, 66, 10] ~~~ >[danger] ##### heappushpop -- 彈出最小值，然后將新參數加入 只彈出添加后最小值，下面的例子當加入的是-3，彈出的是-3 ~~~ import heapq nums = [23,3,5,6,7,-1,5,6,1,10] heap = list(nums) # 先轉換成堆然后再刪除 heapq.heapify(heap) heapq.heappushpop(heap,66) print(heap) 打印結果： [1, 3, 5, 6, 7, 5, 23, 6, 66, 10] ~~~ >[danger] ##### heappush 添加元素 ~~~ import heapq nums = [23,3,5,6,7,-1,5,6,1,10] heap = list(nums) # 先轉換成堆然后再刪除 heapq.heapify(heap) heapq.heappush(heap,66) print(heap) ~~~ >[success] # 實現優先級案例 ~~~ 1. 要有能儲存的堆，也就是列表類型 2. 要設置優先級 3. 要設置插入的順序 ~~~ >[danger] ##### 案例 >實現一個隊列，能夠根據優先級來對元素排序，每次返回優先級最高的 * self._queue 因為heappush的第一個參數給是個列表 * 后面元組的參數依次 優先級，插入的序號，和插入的內容 ~~~ class PriorityQueue: def __init__(self): self._queue = [] self._index = 0 def push(self,item,priority): heapq.heappush(self._queue,(-priority,self._index,item)) self._index += 1 def pop(self): return heapq.heappop(self._queue)[-1] ~~~ * 實現效果 當優先級一樣的時候，先返回，優先插入的 ~~~ class Item: def __init__(self,name): self.name = name def __repr__(self): return self.name q = PriorityQueue() q.push(Item('foo'),1) q.push(Item('fss'),2) q.push(Item('aaa'),1) print(q.pop()) print(q.pop()) print(q.pop()) 打印結果： fss foo aaa ~~~