Python利用heapq实现优先级队列：小顶堆与负数技巧

Evan

发布时间：2026-10-13| 6人浏览过

原创

本文介绍如何使用Python标准库heapq构建优先级队列。因heapq默认生成小顶堆，需将优先级取反后入队以实现高优先级优先弹出。代码通过引入自增索引_index解决优先级相同时的排序稳定性问题，确保先入队的元素先被弹出。

若要构建一个优先级队列，确保每次弹出的元素具有最高优先级，需注意heapq.heapify(list)默认构建的是小顶堆。因此，在将元素推入队列时，需将priority参数转换为相反数（即取负值）后再进行push操作，具体实现代码如下：

import heapq
class PriorityQueue(object):
  """实现一个优先级队列，每次pop优先级最高的元素"""
  def __init__(self):
    self._queue = []
    self._index = 0
  def push(self,item,priority):
    heapq.heappush(self._queue,(-priority,self._index,item))#将priority和index结合使用，在priority相同的时候比较index，pop先进入队列的元素
    self._index += 1
  def pop(self):
    return heapq.heappop(self._queue)[-1]
if __name__ == '__main__':
  pqueue = PriorityQueue()
  pqueue.push('d',4)
  pqueue.push('f',3)
  pqueue.push('a',6)
  pqueue.push('s',2)
  print(pqueue.pop())
  print(pqueue.pop())
  print(pqueue.pop())