二叉堆实现的优先队列

二叉堆的定义

二叉堆是一种完全二叉树，分为两类：

  • 大顶堆：每个节点值 ≥ 子节点值
  • 小顶堆：每个节点值 ≤ 子节点值

基本操作

优先队列主要有两种操作：

  • 入队（heappush）：将新元素加到数组末尾，然后从下往上调整，恢复堆结构。
  • 出队（heappop）：将堆顶元素与末尾元素交换，弹出末尾元素，再对新堆顶自上而下调整，恢复堆结构。

内部实现：

  • 使用heapq模块实现优先队列
  • heapq.heappush(heap, item)：将元素 item 压入堆 heap 中，保持堆结构。
  • heapq.heappop(heap)：弹出并返回堆中的最小元素。
    注意事项：
  • heapq 默认是小顶堆，即每次弹出的是最小值。
  • 如果需实现「大顶堆」（每次弹出最大优先级元素），可将优先级取负数存入堆中。
  • 为保证当优先级相同时元素的入队顺序，通常可额外存储一个自增索引。
1
2
3
4
5
6
7
8
9
10
11
12
import heapq
class PriortyQueue:
	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):
		if not self.queue:
			raise IndexError("pop from empty priorty queue")
		return heapq.heapppop(self.queue)[-1]

应用场景：