Java中如何基于HashMap条目用PriorityQueue创建按值比较的MinHeap

你当前的写法在普通数值范围下可以生效，但存在整数溢出的潜在缺陷，以下是稳妥的实现方案：

原有写法的问题 #

你在比较器中使用o1.getValue() - o2.getValue()返回比较结果，当两个值的差值超出Integer的表示范围（例如一个值为Integer.MAX_VALUE、另一个为负整数）时，减法运算会出现溢出，返回符号错误的结果，最终导致堆排序逻辑完全失效。

推荐实现 #

全版本兼容写法 #

使用Integer类自带的compare方法做比较，从根源规避溢出问题：

PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<Integer, Integer>>() {
    @Override
    public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
        return Integer.compare(o1.getValue(), o2.getValue());
    }
});

Java 8+ 简化写法 #

利用Comparator内置的工具方法和方法引用，可以大幅精简代码：

PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>(
    Comparator.comparingInt(Map.Entry::getValue)
);

额外注意事项 #

• 元素入堆直接调用offer()/add()方法传入HashMap的Entry对象即可，堆顶会始终维护Value最小的条目，调用poll()即可按Value从小到大的顺序取出元素
• 不要直接修改已经入堆的Entry的Value值，PriorityQueue不会自动重排，修改值后需要先将元素移除、更新后再重新入堆才能保证堆结构正确
• 如果需要处理Value相等的场景，可以追加二级排序规则，例如Value相同时按Key升序排列：

PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>(
    Comparator.comparingInt(Map.Entry<Integer, Integer>::getValue)
              .thenComparingInt(Map.Entry::getKey)
);

内容的提问来源于stack exchange，提问作者sumitaccess007