Java PriorityQueue未遵循大顶堆特性问题排查

开发者阿泽

2026-7-22

问题排查：Top K Frequent Elements 实现错误

核心问题：PriorityQueue 不会自动感知外部比较依据的变化
你的自定义Comparator依赖HashMap中的频率值，但PriorityQueue的堆结构仅在元素**入队（add）、出队（poll）、移除（remove）**时触发调整。如果你的实现是边遍历数组统计频率边往堆里加元素，堆中元素的比较逻辑会基于加入时的旧频率，后续HashMap中频率更新后，堆不会自动重新调整结构。
以你的测试用例{3,0,1,0}为例：
1. 遍历到3：频率1，加入堆，堆顶为3
2. 遍历到0：频率1，加入堆，此时所有元素频率相同，若Comparator在频率相同时按数字降序排序，堆顶仍是3
3. 遍历到1：频率1，加入堆，堆顶保持3
4. 遍历到第二个0：频率更新为2，但堆中已存在0且你未重新移除并加入，堆结构仍基于旧频率（所有元素频率为1），最终取堆顶时得到错误的3。
为什么添加最后一个0时仅与自身比较？
如果你维护了大小为K的堆（此处K=1），加入新元素时只会和堆顶元素做一次比较：若判断新元素优先级低于堆顶，会直接丢弃，不会触发更多比较。比如Comparator逻辑写反（把大顶堆写成小顶堆），会错误认为频率更高的0优先级更低，直接跳过堆结构更新，堆顶仍为3。
修复方向
1. 先统计完所有频率，再初始化堆：遍历数组将所有元素频率统计到HashMap后，一次性把HashMap的键放入PriorityQueue。这样每个元素加入堆时的频率都是最终值，堆结构会正确生成。
2. 修正Comparator逻辑：确保大顶堆按频率降序排列，示例Java代码：
```
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> freqMap.get(b) - freqMap.get(a));
```
  频率相同时的排序逻辑不影响高频元素选取，可按需补充。
3. 边统计边维护堆的修正方案：每次更新元素频率后，先调用heap.remove(num)移除旧元素，再重新heap.add(num)，触发堆结构调整。注意remove方法是O(n)复杂度，会影响性能。