Java PriorityQueue自定义Comparator实现二维数组按指定规则插入排序

错误原因梳理 #

• 泛型不匹配：你要存入队列的是长度为2的一维int数组，因此PriorityQueue的泛型应为int[]，对应Comparator的泛型也应该是int[]，你之前写的int[][]和Comparator<Integer>都和实际存储的元素类型不匹配，触发类型转换错误。
• 构造方法使用错误：PriorityQueue不存在「直接传入元素集合+比较器」的构造重载，需要先初始化带自定义比较器的队列，再调用addAll方法批量添加元素。
• 比较逻辑返回值倒置：Comparator的compare方法约定：返回负整数代表第一个参数排在第二个参数之前，返回正整数相反，你原有逻辑的返回值写反会得到倒序结果。
• 方法参数错误：compare方法的参数要和泛型一致，应为两个int[]类型，而非二维数组。

排序逻辑说明 #

你要求的排序规则本质上等价于：先按数组第二个元素升序排列，第二个元素相等时按第一个元素升序排列，完全符合你给出的目标结果。

正确实现代码 #

import java.util.*;
class Check2
{
    public static void main(String[] args) {        
        int events[][]={{1,4},{4,4},{2,2},{3,4},{1,1}};
        // 定义泛型为int[]的优先队列，传入自定义比较器
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                // 先比较第二个元素
                if (a[1] != b[1]) {
                    return a[1] - b[1]; // 第二个元素小的排前面
                } else {
                    // 第二个元素相等时比较第一个元素
                    return a[0] - b[0]; // 第一个元素小的排前面
                }
            }
        });
        // 批量添加元素
        minHeap.addAll(Arrays.asList(events));
        
        // 验证输出：依次弹出队列元素就是目标顺序
        List<int[]> result = new ArrayList<>();
        while (!minHeap.isEmpty()) {
            result.add(minHeap.poll());
        }
        // 打印结果
        for (int[] arr : result) {
            System.out.print(Arrays.toString(arr) + " ");
        }
        // 输出结果：[1, 1] [2, 2] [1, 4] [3, 4] [4, 4]
    }
}

JDK8+ 简化写法 #

如果使用JDK8及以上版本，可以用lambda表达式简化比较器的写法：

PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> {
    if (a[1] != b[1]) return a[1] - b[1];
    return a[0] - b[0];
});

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