堆 解题模板

适用场景

Top K 问题、中位数、合并有序序列、任务调度

通用模板

小顶堆 / 大顶堆

 
import heapq
 
heap = []                     # 默认小顶堆
 
heapq.heappush(heap, val)     # 入堆 O(log k)
 
smallest = heap[0]            # 查看堆顶 O(1)
 
heapq.heappop(heap)           # 弹出堆顶 O(log k)
 
# 大顶堆：存负数
 
big_heap = []
 
heapq.heappush(big_heap, -val)
 
largest = -big_heap[0]
 

Top K 小顶堆

 
heap = []
 
for num in nums:
 
    heapq.heappush(heap, num)
 
    if len(heap) > k:
 
        heapq.heappop(heap)  # 保持大小为 k
 
return heap[0]  # 第 k 大
 

双堆找中位数

 
small = []  # 大顶堆（负数）
 
large = []  # 小顶堆
 
# findMedian: small[0] 或 (small[0]+large[0])/2
 

复杂度总结

模式	时间	空间	典型题
单堆	O(n log k)	O(k)	第K大、前K高频
双堆	O(log n)	O(n)	数据流中位数
桶排序	O(n)	O(n)	前K高频（频率桶）

关键要点

• Python heapq 只有小顶堆

• Top K 用小顶堆不是大顶堆

• 堆 + 哈希表：频率统计后入堆

→ 查看该分类题目：LeetCode学习路线图 > 六、堆

---

关联题型

关联题型	常见结合方式	典型题目
排序	堆排序 vs 快速选择	215第K大元素
贪心	堆维护当前最优	621任务调度器
图论	Dijkstra 最小堆优化	743网络延迟时间