Java 对象比较详解：Comparable、Comparator 与 PriorityQueue 实战

Object 类中提供了 equals 方法，但默认实现也是比较地址。如果我们需要比较对象的内容（例如两张牌点数和花色都相同），就需要重写相关方法。

三种比较方案

1. 重写 equals 方法

重写的标准套路通常如下：

1. 检查是否指向同一个对象（this == o）。
2. 检查传入对象是否为 null。
3. 检查类型是否匹配（instanceof）。
4. 按照业务目标完成内容比较。

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || !(o instanceof Card)) return false;
    Card c = (Card) o;
    return rank == c.rank && suit.equals(c.suit);
}

注意：equals 只能判断相等，无法处理大于、小于的关系，因此不适合用于排序场景。

2. 实现 Comparable 接口

如果需要定义类的自然排序顺序，可以让类实现 Comparable 接口并重写 compareTo 方法。

public class Card implements Comparable<Card> {
    public int rank;
    public String suit;
    public Card(int rank, String suit) {
        this.rank = rank;
        this.suit = suit;
    }

    @Override
    public int compareTo(Card o) {
        if (o == null) return 1;
        return this.rank - o.rank;
    }
}

返回值为负数表示当前对象小，0 表示相等，正数表示大。这是 JDK 提供的泛型接口，位于 java.lang 包下，可直接使用。

3. 使用 Comparator 接口

当无法修改原类，或者需要多种排序规则时，可以使用外部比较器 Comparator。

class CardComparator implements Comparator<Card> {
    @Override
    public int compare(Card o1, Card o2) {
        if (o1 == o2) return 0;
        if (o1 == null) return -1;
        if (o2 == null) return 1;
        return o1.rank - o2.rank;
    }
}

// 使用时
PriorityQueue<Card> pq = new PriorityQueue<>(new CardComparator());

Comparator 位于 java.util 包，需导入。它允许在不修改类源码的情况下定制比较逻辑。

PriorityQueue 的比较方式

集合框架中的 PriorityQueue 底层依赖堆结构，内部元素必须可比较。它支持两种比较策略：

1. Comparable：默认内部比较方式。如果插入的自定义对象实现了该接口并覆写了 compareTo，则自动生效。
2. Comparator：用户提供的比较器对象。构造 PriorityQueue 时传入一个实现了 Comparator 接口的实例。

查看 PriorityQueue 源码可知，其内部维护了一个 Comparator 成员变量。如果未提供比较器，则为 null，此时调用 siftUpComparable；否则调用 siftUpUsingComparator。理解这一机制有助于我们在实际开发中灵活选择排序策略。

利用 PriorityQueue 解决 Top-K 问题

Top-K 问题是寻找最大或最小的前 K 个数据。例如找出数组中最小的 K 个数。

常规做法是排序后取前 K 个，但效率较低。更高效的方法是利用堆的特性：

• 求最小 K 个数：维护一个大小为 K 的大顶堆。遍历数组，若当前元素小于堆顶，则替换堆顶并调整堆。
• 求最大 K 个数：维护一个大小为 K 的小顶堆。

这样堆中保留的 K 个元素即为所求结果。

下面给出基于 PriorityQueue 的实现示例，重点在于通过 Comparator 创建大根堆：

class IntCmp implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1; // 降序排列，形成大顶堆
    }
}

class Solution {
    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        if (arr == null || k <= 0) return ret;

        // 创建大根堆
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new IntCmp());
        
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }

        for (int j = k; j < arr.length; j++) {
            int top = priorityQueue.peek();
            if (top > arr[j]) {
                priorityQueue.poll();
                priorityQueue.offer(arr[j]);
            }
        }

        for (int i = 0; i < k; i++) {
            ret[i] = priorityQueue.poll();
        }
        return ret;
    }
}

时间复杂度分析：建堆 O(K)，遍历剩余元素 O((N-K)logK)，总体复杂度约为 O(N log K)。相比全排序 O(N log N)，在 N 远大于 K 时优势明显。