使用优先队列时，比较器有哪些常见坑？

简化版

优先队列的比较器决定堆序，比较器写错会直接导致结果错。

常见坑包括：用减法比较导致整数溢出、比较规则不满足传递性、相等时没有稳定的 tie-breaker、修改已入堆对象字段但不重新调整堆。

面试中要强调：堆不会自动感知对象字段变化，比较器也必须保持一致、稳定、可传递。

详细版

优先队列内部依赖比较器判断父子节点是否满足堆序。如果比较器不可靠，堆结构就无法保证正确。

常见问题如下：

坑	后果
`a - b` 比较	可能溢出
比较规则不传递	堆序无法定义
入堆后修改字段	堆不会自动重排
相等元素无 tie-breaker	结果顺序不稳定

例如 Java 里更推荐：

PriorityQueue<int[]> pq = new PriorityQueue<>(
    (a, b) -> Integer.compare(a[0], b[0])
);

而不是 (a, b) -> a[0] - b[0]。

完整版教学

1. 比较器为什么是优先队列的生命线

优先队列本质上只维护一个堆序关系。

对于小顶堆来说，比较器告诉它「谁更小，谁应该更靠近堆顶」。

如果比较器有问题，堆的上浮、下沉都会基于错误判断执行，最终堆顶就不可信。

堆的正确性依赖比较器定义出稳定的一致顺序。

2. 减法比较为什么危险

很多人会写：

(a, b) -> a.priority - b.priority

如果 a.priority 很大，b.priority 很小，减法可能溢出，符号反转。

更安全的写法是：

(a, b) -> Integer.compare(a.priority, b.priority)

对于 long 类型，用：

(a, b) -> Long.compare(a.time, b.time)

这个坑在定时任务、时间戳、距离值里尤其常见。

3. 比较规则必须满足传递性

比较器应该满足：

如果 a < b 且 b < c，那么 a < c

如果比较规则依赖随机数、当前时间、外部可变状态，就可能破坏传递性。

例如：

compare(a, b) 根据当前系统负载返回不同结果

这种比较器会让同一对元素在不同时刻得出不同顺序，堆无法稳定维护。

4. 相等时为什么要考虑 tie-breaker

如果两个元素优先级相等，比较器返回 0。

这不一定错，但如果业务要求稳定顺序，就需要补一个 tie-breaker。

场景	tie-breaker
定时任务	创建序号
多路归并	来源列表编号
排行榜	用户 id
日志处理	原始顺序

例如：

Comparator<Task> cmp = Comparator
    .comparingLong((Task t) -> t.expireAt)
    .thenComparingLong(t -> t.sequence);

5. 入堆对象字段变化为什么不会自动重排

优先队列不是响应式结构。

对象入堆后，如果你修改了影响比较的字段，堆不会自动知道。

task.priority = 1; // 已经在堆里

此时 task 可能应该上浮，但堆没有触发上浮操作。

正确做法通常是：

删除后重新插入；
使用索引优先队列执行 changePriority；
插入新版本，旧版本懒删除。

6. 大顶堆和小顶堆不要写反

很多语言默认是小顶堆，比如 Java PriorityQueue。

如果要大顶堆，可以反转比较：

(a, b) -> Integer.compare(b.score, a.score)

但要注意仍然不能写成 b.score - a.score，因为同样可能溢出。

7. 多字段比较要表达清楚业务优先级

如果元素有多个字段，例如 (score, time, id)，必须明确排序层级。

优先级	规则
第 1 关键字	分数高优先
第 2 关键字	时间早优先
第 3 关键字	id 小优先

比较器应该对应业务规则，而不是随手拼字段。

8. 常见误区与追问

误区：比较器只影响顺序，不影响正确性。 比较器错误会让堆顶元素错误，直接影响算法结果。
误区：用减法比较更简洁也安全。 整数溢出会导致比较结果反转，应使用 Integer.compare 或 Long.compare。
误区：修改入堆对象字段后堆会自动调整。 堆不会感知字段变化，必须重新插入或显式调整。
追问：优先级相等时一定要 tie-breaker 吗？ 不一定，只有业务要求稳定顺序或可重复结果时才必须加。
追问：比较器能依赖外部状态吗？ 尽量不要，外部状态变化会破坏比较一致性。

简化版

详细版