优先队列自定义排序java

### Java 中实现优先队列的自定义排序

在 Java 中，`PriorityQueue` 默认按照元素的自然顺序进行排列。为了实现自定义排序，可以在创建 `PriorityQueue` 的时候提供一个 `Comparator` 接口的实例。

#### 使用 Comparator 进行自定义排序

当希望改变 `PriorityQueue` 的默认行为时，比如从最小堆变为最大堆或是根据特定属性排序复杂对象，则需传递一个实现了 `compare(T o1, T o2)` 方法的对象给构造函数[^1]。

对于基本数据类型的封装类（如 Integer），可以直接通过 lambda 表达式快速指定比较逻辑：

import java.util.PriorityQueue;
import java.util.Comparator;

public class CustomSortExample {
    public static void main(String[] args) {
        // 创建一个最大堆的优先队列
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
                return b - a;  // 反转比较操作符以获得最大堆效果
            }
        });

        // 或者更简洁的方式使用lambda表达式
        PriorityQueue<Integer> maxHeapLambda = new PriorityQueue<>((a, b) -> b - a);

        // 测试插入几个整数并打印出来验证是否按预期工作
        maxHeap.addAll(java.util.Arrays.asList(10, 5, 20, 15));
        while (!maxHeap.isEmpty()) {
            System.out.println(maxHeap.poll());
        }

        // 对于maxHeapLambda同样适用上述测试代码...
    }
}

这段程序展示了两种不同的方法来初始化具有相反顺序的最大堆：一种是匿名内部类形式；另一种则是利用 Lambda 表达式的简化版本[^2]。

#### 处理复杂对象的情况

如果要处理的是非基础类型的数据结构，例如包含多个字段的学生记录，那么就需要更加详细的定制化方案。此时应该让这些实体类要么自己实现 `Comparable<T>` 接口，要么向 `PriorityQueue` 提供外部的 `Comparator` 来指导其如何对比两个不同学生之间的关系。

假设有一个 Student 类型，并且想要依据成绩降序建立学生的优先级列表：

class Student implements Comparable<Student> {
    private String name;
    private double score;

    public Student(String n, double s) {
        this.name = n;
        this.score = s;
    }

    @Override
    public int compareTo(Student otherStudent) {
        return Double.compare(otherStudent.score, this.score);
    }

    @Override
    public String toString() {
        return "Name=" + name + ", Score=" + score;
    }
}

// 现在可以简单地将此类型放入到 Priority Queue 当中而无需额外配置，
// 因为我们已经在 Student 类里边重写了compareTo方法。
PriorityQueue<Student> studentPQ = new PriorityQueue<>();
studentPQ.offer(new Student("Alice", 98.5));
studentPQ.offer(new Student("Bob", 76.3));
while(!studentPQ.isEmpty()){
    System.out.println(studentPQ.poll());
}

在这个例子中，由于已经为 `Student` 定义了一个合理的 `compareTo()` 函数，所以即使不显式给出任何参数也能得到期望的结果——即总是先弹出分数最高的那个同学的信息。