堆的接口只有 offer / poll / peek，用起来像个干净的抽象；出问题的地方几乎全在抽象之外：建堆方式选错、比较器写错、把非线程安全当线程安全、以为能有序遍历。这些都不会抛异常，只会让结果慢慢偏掉。
先把四条结论摆出来：PriorityQueue 是小顶堆、迭代器无序、非线程安全、删除中间元素是 O(n)。记住这四条，下面九成的坑不必踩。
1. 堆的性质与数组表示
堆是"完全二叉树 + 堆序"：每层填满才往下一层放，且每个节点都不大于（小顶）或不小于（大顶）它的孩子。完全二叉树这一条让它能平铺进数组，不需要指针。
// 下标关系：0-based
int parent(int i) { return (i - 1) >>> 1; }
int left(int i) { return (i << 1) + 1; }
int right(int i) { return (i << 1) + 2; }
| 关系 | 0-based 公式 | 说明 |
|---|---|---|
| 父 / 左 / 右 | (i-1)/2、2i+1、2i+2 |
孩子下标 ≥ n 即不存在 |
| 最后一个非叶节点 | n/2 - 1 |
建堆下沉的起点 |
| 高度 | ⌊log₂n⌋ |
决定 offer/poll 的 O(log n) |
堆序只保证"根是极值"，不保证任何其他顺序。所以"第二大元素在哪"没有答案——可能是根的任一孩子，也可能更深。
2. 上浮、下沉与两种建堆
static void swap(int[] h, int i, int j) { int t = h[i]; h[i] = h[j]; h[j] = t; }
static void siftUp(int[] h, int i) { // 插入
while (i > 0 && h[(i - 1) >>> 1] > h[i]) {
int p = (i - 1) >>> 1;
swap(h, p, i);
i = p;
}
}
static void siftDown(int[] h, int i, int n) { // 删堆顶与建堆
while (true) {
int l = (i << 1) + 1, r = l + 1, m = i;
if (l < n && h[l] < h[m]) m = l;
if (r < n && h[r] < h[m]) m = r;
if (m == i) break; // 已是三者最小
swap(h, m, i);
i = m;
}
}
插入走上浮（新元素放末尾，逆序就与父亲交换）；删堆顶走下沉（末尾元素搬到根，再一路和较小的孩子换）。
建堆有两种写法，代价差一个 log：
| 方式 | 代码 | 复杂度 | 说明 |
|---|---|---|---|
| 逐个插入 | for (int x : a) { h[n++] = x; siftUp(h, n-1); } |
O(n log n) | 每次插入最多上浮到根 |
| 自底向下沉 | for (int i = n/2 - 1; i >= 0; i--) siftDown(h, i, n); |
O(n) | 大部分节点在底层，下沉距离很短 |
O(n) 的来源值得记住：高度 h 的节点约 n/2^(h+1) 个，每个最多下沉 h 步，Σ h·n/2^(h+1) 收敛到 O(n)。代价按节点高度而非节点数计，绝大多数节点根本不下沉。
static void heapify(int[] h) {
for (int i = h.length / 2 - 1; i >= 0; i--) siftDown(h, i, h.length);
}
i 必须从 n/2 - 1 递减，保证下沉时两棵子树已经是堆。
3. PriorityQueue 的默认行为与比较器
默认是小顶堆，按自然序（Comparable）比较。要大顶堆有几种写法，选哪种只看可读性与溢出风险：
PriorityQueue<Integer> min = new PriorityQueue<>(); // 小顶（默认）
PriorityQueue<Integer> max1 = new PriorityQueue<>(Comparator.reverseOrder());
PriorityQueue<Integer> max2 = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
其中 reverseOrder() 最该优先用；-x 与存负数都有溢出隐患（Integer.MIN_VALUE 取负还是它自己），只适合值域已知为正的场合，别进主干代码。
绝对不要写 (a, b) -> a - b。差值在 int 上会溢出：a = 2_000_000_000, b = -2_000_000_000 时结果溢出成负数，比较器给出反序，堆序当场坏掉——而 poll 照样返回"某个值"，只是不是极值。
自定义对象要小心两件事：比较器必须全序且与 equals 一致（否则行为未定义），以及入堆后字段不能再变。
4. Top-K 与数据流第 K 大
求前 K 大，直觉是"大顶堆"，正确做法却是大小为 K 的小顶堆：
static int[] topK(int[] nums, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<>(k + 1); // 小顶堆
for (int x : nums) {
heap.offer(x);
if (heap.size() > k) heap.poll(); // 弹掉当前第 k+1 大的
}
int[] out = new int[heap.size()];
for (int i = out.length - 1; i >= 0; i--) out[i] = heap.poll();
return out;
}
反直觉点的解释：堆顶是候选集里最小的那个，也就是第 K 大的守门员。新元素比守门员大才有资格进来，进来后旧守门员被弹掉。堆里始终只有 K 个元素，内存 O(K)、时间 O(n log K)。
| 方案 | 时间 | 额外空间 | 何时用 |
|---|---|---|---|
| 全排序 | O(n log n) | O(n) | K 接近 n，或本来就要全序 |
| 大小 K 的堆 | O(n log K) | O(K) | K 远小于 n、数据流、内存受限 |
| 快速选择 | 期望 O(n)，最坏 O(n²) | O(1) | 一次性、可改动原数组 |
数据流的第 K 大就是同一结构长期驻留：来一个 offer 一个，超了就 poll，任意时刻 peek() 即第 K 大。要同时支持第 K 大与第 K 小，就维护两个堆并保持总量为 K。
5. 合并 K 个有序链表与多路归并
static ListNode mergeK(ListNode[] lists) {
PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.val));
for (ListNode h : lists) if (h != null) pq.offer(h);
ListNode dummy = new ListNode(0), tail = dummy;
while (!pq.isEmpty()) {
ListNode n = pq.poll();
tail.next = n;
tail = n;
if (n.next != null) pq.offer(n.next); // 只补回刚被取走那条链的下一个
}
return dummy.next;
}
这就是多路归并：堆里始终只有 K 个"各链当前头"，每次取全局最小、再补一个，代价 O(N log K)。K = 2 时它退化成两两归并、常数更小，所以两路归并不需要堆。不用全排序的原因是规模：多路归并是流式的，只需 K 个指针常驻。
6. 延迟队列与惰性删除
定时任务的最小实现是把"到期时间"当 key 放进堆：到期的 take 出来执行，没到期就等。
final class DelayTask implements Delayed {
private final long expireAt = System.nanoTime() + delayNanos; // 绝对时间戳
public long getDelay(TimeUnit u) { return u.convert(expireAt - System.nanoTime(), TimeUnit.NANOSECONDS); }
public int compareTo(Delayed o) { return Long.compare(expireAt, ((DelayTask) o).expireAt); }
}
DelayQueue<DelayTask> queue = new DelayQueue<>(); // take() 会阻塞到最早任务到期
生产代码更常见的是惰性删除：取消时不去堆里删（那是 O(n) 还要加锁），只在取消集合里记一笔，出堆时检查并丢弃。
堆在定时场景的局限很清楚：它只能高效地取最小、删最小。业务一旦涉及"随机取消"，只能靠惰性删除兜底，废弃任务堆积会让堆无谓变大。
7. 双堆求中位数与快速选择的取舍
中位数是"动态求第 K 小、且 K 随规模变化"，堆正合适：大顶堆存较小的一半，小顶堆存较大的一半，两个堆顶就是中位数的候选。
final class MedianFinder {
private final PriorityQueue<Integer> lo = new PriorityQueue<>(Comparator.reverseOrder()); // 较小半，大顶
private final PriorityQueue<Integer> hi = new PriorityQueue<>(); // 较大半，小顶
void add(int x) {
if (lo.size() == hi.size()) { lo.offer(x); hi.offer(lo.poll()); }
else { hi.offer(x); lo.offer(hi.poll()); } // 保证 hi.size() ∈ {lo.size(), lo.size()+1}
}
double median() { return lo.size() == hi.size() ? (lo.peek() + hi.peek()) / 2.0 : hi.peek(); }
}
不变量只有一条：lo.size() <= hi.size() <= lo.size() + 1，且 lo 的每个元素 ≤ hi 的每个元素。add 里"先进后出"（offer 进去再弹出来）就是在强制这条不变量。
选型很干脆：一次性求第 K 小用快速选择或排序（期望 O(n)、无需额外结构）；数据流持续插入、随时要中位数用双堆（插入 O(log n)、查询 O(1)）。快速选择的代价藏在最坏情况：枢轴总取到端点时退化成 O(n²)，随机枢轴只是压概率而非保证。
8. 排错：六种"取出来的不是极值"
| 现象 | 原因 | 处理 |
|---|---|---|
| 比较器偶发反序、结果乱 | (a, b) -> a - b 差值溢出 |
改 Integer.compare / Comparator.comparingInt |
| 改了入堆对象的字段后顺序全乱 | 堆序在入堆时确定，改字段不会重排 | 对象入堆后视为不可变，要改就先删再插 |
并发下丢元素或 size 异常 |
PriorityQueue 非线程安全 |
换 PriorityBlockingQueue 或外部加锁 |
remove(x) 很慢 |
按 equals 线性查找，O(n) |
改惰性删除，或用 TreeMap / 索引堆 |
| 遍历得到乱序 | iterator() 按数组下标遍历 |
要顺序就反复 poll |
| 双堆查询差一 | 两堆大小差超过 1 | add 里统一走"先进后出" |
遍历那条值得单独强调：PriorityQueue 的迭代器只保证"每个元素出现一次"，完全不承诺顺序。日志里 pq.toString() 乱序不是 bug，拿它当有序列表用才是。
9. 边界：什么需求堆本来就不合适
| 需求 | 更好的结构 | 原因 |
|---|---|---|
| 只要区间最值、还要滑动删除 | 单调队列 / 线段树 | 堆删非堆顶元素是 O(n) |
| 频繁按键取值、要前驱后继 | TreeMap |
天然有序 + O(log n) 删除 |
| 只需要一次性最小/最大 | 一次线性扫描 | 建堆是 O(n)，但常数更大 |
| 优先级队列 + 阻塞语义 | PriorityBlockingQueue |
自带锁与条件等待 |
| 定时任务数万以上 | 时间轮 | 堆的 O(log n) 与锁竞争成为瓶颈 |
| 需要同优先级稳定出队 | 比较器加序号做次关键字 | 堆本身不保证稳定性 |
| 元素几乎有序 | 插入排序 | 近似有序时它是 O(n + 逆序对) |
最后一条最常被忽略：元素近乎有序时，堆是拿优势换通用性——插入排序在这种输入上是 O(n + 逆序对)，堆仍是 O(n log n)。
10. 自测
- 堆的数组表示里，为什么建堆要从
n/2 - 1递减，而不是从 0 递增？ - 自底向下的
heapify为什么是 O(n)，而逐个插入是 O(n log n)？代价是按什么求和的？ - 求前 K 大为什么用小顶堆？堆顶在算法里扮演什么角色？
(a, b) -> a - b在什么输入下会让堆序坏掉？坏掉后poll会抛异常吗？- 为什么
PriorityQueue的iterator()不能当作有序遍历用？要按序取出该怎么做？ - 定时任务需要"随机取消"，堆为什么不适合？替代结构是什么？