堆适合反复取得当前最小或最大候选，并在只关心 K 个结果时避免完整排序。

🧭 什么时候考虑这个专题

需要动态极值或 Top K 时考虑堆；持续中位数使用双堆；合并多路有序流时只保留每路当前头部。

开始编码前先明确输入、输出、数据规模和允许修改的数据，再用一句话写出循环、窗口、堆或递归函数保持的不变量。

核心结构与复杂度

知识点核心规则常见复杂度
建堆复杂度对完整数组自底向上 Heapify 可以在 O(n) 时间建堆Heapify O(n)
堆操作成本查看堆顶 O(1)，入堆和出堆通常 O(log n)入堆出堆 O(log n)
Top K 小根堆维护大小为 K 的小根堆可在 O(n log k) 找最大 K 项O(n log k)
.NET PriorityQueue 方向PriorityQueue 默认优先移除最小 Priority入队出队 O(log n)
双堆中位数最大堆保存较小一半，最小堆保存较大一半插入 O(log n)，查询 O(1)

复杂度必须对应真实代码路径。哈希结构要区分平均与最坏情况，递归要计算调用栈，返回结果是否计入空间也应按题目口径说明。

适用边界

  • 建堆复杂度： 逐个执行 n 次入堆则是 O(n log n)
  • 堆操作成本： 在堆中查找任意值仍可能需要 O(n)
  • Top K 小根堆： K 接近 n 时排序方案可能更简单
  • .NET PriorityQueue 方向： 实现最大堆需反转优先级或使用自定义比较器
  • 双堆中位数： 两堆大小差不超过一且所有左侧值不大于右侧值

C# 实现检查

  1. 方法签名与题目契约一致，不依赖控制台输入输出。
  2. 数值计算检查 int 溢出，必要时先提升为 long。
  3. 集合选择说明平均复杂度、顺序语义和重复值处理。
  4. 字符串题明确使用 char、Rune、序号比较还是文化比较。
  5. 递归题说明终止条件、最大深度和退化输入。

⚠️ 常见误区

  • 建堆复杂度： 不要把“任何建堆方式都必然是 O(n log n)”当成规则。
  • 堆操作成本： 不要把“堆中所有查询都和堆顶查询一样是 O(1)”当成规则。
  • Top K 小根堆： 不要把“Top K 必须先完整排序所有元素”当成规则。
  • .NET PriorityQueue 方向： 不要把“PriorityQueue 默认总是最大堆”当成规则。
  • 双堆中位数： 不要把“只维护两个堆的大小就能保证中位数正确”当成规则。

练习顺序

先完成本组 5 道选择题，口述每个选项的边界；再独立实现编程题，最后对照参考答案检查不变量、复杂度和面试追问。