堆

堆的核心价值是：始终快速拿到当前最值。如果哈希表擅长“查有没有”，那堆擅长“当前最小/最大的是谁”。

核心能力

• 插入一个元素：O(log n)
• 删除堆顶：O(log n)
• 查看堆顶最值：O(1)

两种常见形态

1. 小根堆

   • 堆顶是当前最小值
   • 常用于维护最大的 k 个元素、最短路、最小代价

2. 大根堆

   • 堆顶是当前最大值
   • 常用于维护最小的 k 个元素、Top K 反向问题

典型题型

• Top K
• Merge K Sorted Arrays / Lists
• 数据流中的中位数
• Dijkstra / Best First Search
• 第 n 个丑数、k 路归并

什么时候该想到堆

• 需要动态维护“当前最优 / 最差”的那个元素
• 数据是一边到来一边处理，不能整体排序后再做
• 每次只关心前 k 个或当前极值

和排序的区别

• 排序：一次性把整体排好
• 堆：更适合边读边维护最值，尤其是在线问题

常见坑

• 只会把堆当排序工具，不会把它当“动态最值结构”
• Top K 时大小堆方向想反
• 忘记堆只能保证堆顶是最值，不能保证整体有序

延伸

• 如果题目还需要快速删除中间节点、快速定位对象，往往需要和哈希表配合，参考 21. 哈希表和堆