Python中使用heapq处理优先级队列的平局决胜问题

核心思路 #

利用heapq模块的原生堆操作，通过构造自定义排序键满足需求：

• heapq默认是小顶堆，按元组元素顺序升序比较
• 针对「先按数值降序，数值相同则按字符串字典序升序」的规则，将原元组(name, score)转换为(-score, name)作为堆的存储元素：
  • -score实现数值降序（小顶堆中-score越小，原score越大，优先级越高）
  • name保证数值相同时，字典序小的元素优先级更高

代码实现 #

初始化堆并批量入队

import heapq

values = [("aaa", 10), ("bbb", 10), ("ccc", 10), ("David", 15)]
heap = []

# 批量插入元素到堆中
for name, score in values:
    heapq.heappush(heap, (-score, name))

频繁入队/出队操作

# 新增元素入队
heapq.heappush(heap, (-12, "Bob"))

# 出队获取优先级最高的元素（循环弹出直到堆为空）
while heap:
    neg_score, name = heapq.heappop(heap)
    print(f"{name}: {-neg_score}")

输出结果

David: 15
Bob: 12
aaa: 10
bbb: 10
ccc: 10

优势说明 #

• 完全基于heapq原生的heappush和heappop操作，时间复杂度均为O(log n)，适合高频入队出队场景
• 无需依赖cmp_to_key或nlargest，避免额外性能开销，实现简洁高效

内容的提问来源于stack exchange，提问作者Andrew Qian