Python中heapq模塊 堆隊列算法heapq的優先級隊列實現

在python中，使用heapq模塊可以很方便地實現優先級隊列。堆（heap）是一種特殊的樹結構，常用于快速獲取最小值或最大值的場景。heapq默認實現的是最小堆，也就是說堆頂元素始終是整個堆中最小的那個。

什么是優先級隊列？

優先級隊列是一種數據結構，每個元素都帶有一個“優先級”。當訪問或刪除元素時，優先級更高的元素會優先被處理。比如任務調度、醫院掛號系統等場景都會用到這種結構。

常見的做法是將每個元素和它的優先級打包成一個元組，然后插入堆中。python的heapq會根據元組的第一個元素進行排序，從而實現優先級控制。

如何用heapq創建優先級隊列

使用heapq實現優先級隊列非常簡單，只需要導入模塊并維護一個堆列表即可：

• 使用heapq.heappush()添加元素
• 使用heapq.heappop()彈出當前優先級最高的元素（即最小的）

例如：

立即學習“Python免費學習筆記（深入）”；

import heapq  queue = [] heapq.heappush(queue, (3, '寫報告')) heapq.heappush(queue, (1, '回郵件')) heapq.heappush(queue, (2, '開會'))  print(heapq.heappop(queue))  # 輸出：(1, '回郵件')

每次調用heappop()都會取出當前優先級最高的任務。

注意：如果兩個元素的優先級相同（比如都是2），那么它們之間的順序取決于后面的元素內容，在heapq中不保證穩定排序。

處理優先級相同的情況

當多個任務擁有相同的優先級時，你可能還希望這些任務能按照它們插入的順序來處理。這時候可以在元組中加入第三個字段，比如時間戳：

import heapq import time  queue = [] timestamp = 0  def add_task(priority, task):     global timestamp     heapq.heappush(queue, (priority, timestamp, task))     timestamp += time.time()  add_task(2, '任務A') add_task(2, '任務B') add_task(1, '緊急任務')  print(heapq.heappop(queue))  # 緊急任務先出 print(heapq.heappop(queue))  # A比B早添加，所以先出 print(heapq.heappop(queue))  # 最后才是B

這樣即使優先級相同，也能通過時間戳保持插入順序。

常見問題與注意事項

• heapq默認是最小堆，如果你需要最大堆行為，可以把優先級取負數再插入。

  heapq.heappush(queue, (-priority, task))

• 不要直接操作堆列表，比如用append()而不是heappush()，這會導致堆結構損壞。

• heapq適用于中小型數據量。如果數據特別大或者頻繁操作，要考慮其他結構如線段樹、平衡樹等。

基本上就這些。heapq雖然簡單，但配合元組使用就能輕松實現優先級隊列功能，適合很多實際場景。只要注意好插入和彈出的方式，以及優先級沖突的處理方式，基本不會出錯。