如何实现支持Comparable与Comparator的Java泛型优先队列

嘿，这个问题问到点子上了——Java标准库的有序集合（像PriorityQueue、TreeSet）之所以能同时支持Comparable元素和外部Comparator，核心就是在内部维护了一个可选的比较器实例，咱们自己实现自定义优先队列的时候，完全可以照搬这个思路。我给你一步步拆解具体怎么搞：

第一步：定义泛型类与核心成员 #

首先，咱们的自定义优先队列类要声明为泛型类，同时内部要维护两个核心东西：

• 存储元素的容器（比如用ArrayList或者数组，这里用ArrayList做示例）
• 一个可选的Comparator<? super E>实例——如果这个实例不为null，就用它来比较元素；如果为null，就默认使用元素自身的Comparable接口。

代码示例：

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class CustomPriorityQueue<E> {
    // 存储元素的容器
    private List<E> elements;
    // 内部比较器，null表示使用元素的Comparable接口
    private Comparator<? super E> comparator;

    // 无参构造器：要求元素必须实现Comparable接口
    public CustomPriorityQueue() {
        this.comparator = null;
        this.elements = new ArrayList<>();
    }

    // 带Comparator的构造器：不要求元素实现Comparable
    public CustomPriorityQueue(Comparator<? super E> comparator) {
        this.comparator = comparator;
        this.elements = new ArrayList<>();
    }
}

第二步：实现通用的比较逻辑 #

接下来要写一个私有方法，统一处理两种比较场景——这样后面的堆调整逻辑（上浮、下沉）就不用重复判断了。这里要注意，如果comparator为null，我们需要把元素强制转换为Comparable<? super E>，如果元素没实现这个接口，运行时会抛出ClassCastException，这和Java标准库的行为完全一致，是合理的。

@SuppressWarnings("unchecked")
private int compare(E a, E b) {
    if (comparator != null) {
        // 使用外部传入的比较器
        return comparator.compare(a, b);
    } else {
        // 使用元素自身的Comparable接口
        return ((Comparable<? super E>) a).compareTo(b);
    }
}

第三步：实现核心的堆操作（以小顶堆为例） #

优先队列的核心是堆结构，所以我们需要实现入队（offer）时的上浮调整，以及出队（poll）时的下沉调整，这两个操作都会用到上面的compare方法。

入队（offer）与上浮 #

public boolean offer(E e) {
    if (e == null) {
        throw new NullPointerException(); // 和标准库一致，不允许null元素
    }
    elements.add(e);
    // 把新加入的元素上浮到合适位置
    siftUp(elements.size() - 1);
    return true;
}

private void siftUp(int index) {
    E key = elements.get(index);
    // 从当前节点往上找父节点，直到找到合适的位置
    while (index > 0) {
        int parentIndex = (index - 1) / 2;
        E parent = elements.get(parentIndex);
        // 如果当前元素不比父元素小，说明位置正确，停止上浮
        if (compare(key, parent) >= 0) {
            break;
        }
        // 交换当前节点和父节点
        elements.set(index, parent);
        index = parentIndex;
    }
    elements.set(index, key);
}

出队（poll）与下沉 #

public E poll() {
    if (elements.isEmpty()) {
        return null;
    }
    int lastIndex = elements.size() - 1;
    // 取出堆顶元素（优先级最高的元素）
    E result = elements.get(0);
    // 把最后一个元素移到堆顶，然后下沉调整
    E last = elements.remove(lastIndex);
    if (lastIndex > 0) {
        elements.set(0, last);
        siftDown(0);
    }
    return result;
}

private void siftDown(int index) {
    int size = elements.size();
    E key = elements.get(index);
    int half = size / 2;
    // 只需要遍历到堆的中间位置，因为叶子节点没有子节点
    while (index < half) {
        int leftChildIndex = 2 * index + 1;
        E leftChild = elements.get(leftChildIndex);
        int rightChildIndex = leftChildIndex + 1;
        E rightChild = null;
        int minChildIndex = leftChildIndex;

        // 如果有右子节点，比较左右子节点，找到更小的那个
        if (rightChildIndex < size) {
            rightChild = elements.get(rightChildIndex);
            if (compare(leftChild, rightChild) > 0) {
                minChildIndex = rightChildIndex;
                leftChild = rightChild;
            }
        }

        // 如果当前元素比最小的子节点还小，说明位置正确，停止下沉
        if (compare(key, leftChild) <= 0) {
            break;
        }
        // 交换当前节点和最小的子节点
        elements.set(index, leftChild);
        index = minChildIndex;
    }
    elements.set(index, key);
}

第四步：添加辅助方法（可选但实用） #

比如获取堆顶元素的peek、判断是否为空的isEmpty、获取大小的size：

public E peek() {
    return elements.isEmpty() ? null : elements.get(0);
}

public boolean isEmpty() {
    return elements.isEmpty();
}

public int size() {
    return elements.size();
}

两种使用场景示例 #

场景1：元素实现Comparable接口 #

当元素自己实现了Comparable时，直接用无参构造器即可：

class Task implements Comparable<Task> {
    private int priority;
    private String name;

    public Task(int priority, String name) {
        this.priority = priority;
        this.name = name;
    }

    @Override
    public int compareTo(Task o) {
        // 优先级数值越小，优先级越高（小顶堆）
        return Integer.compare(this.priority, o.priority);
    }

    @Override
    public String toString() {
        return name + "(优先级: " + priority + ")";
    }
}

// 使用无参构造器
public static void main(String[] args) {
    CustomPriorityQueue<Task> taskQueue = new CustomPriorityQueue<>();
    taskQueue.offer(new Task(5, "写项目文档"));
    taskQueue.offer(new Task(1, "修复线上bug"));
    taskQueue.offer(new Task(3, "开发新功能"));

    while (!taskQueue.isEmpty()) {
        System.out.println(taskQueue.poll());
    }
    // 输出顺序：修复线上bug(优先级: 1) → 开发新功能(优先级: 3) → 写项目文档(优先级: 5)
}

场景2：元素未实现Comparable，传入外部Comparator #

如果元素没有实现Comparable，我们只需要在构造时传入一个自定义的Comparator即可：

class Person {
    private int age;
    private String name;

    public Person(int age, String name) {
        this.age = age;
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    @Override
    public String toString() {
        return name + "(年龄: " + age + ")";
    }
    // 没有实现Comparable接口
}

// 使用带Comparator的构造器
public static void main(String[] args) {
    // 按年龄从小到大排序的比较器
    Comparator<Person> ageComparator = Comparator.comparingInt(Person::getAge);
    CustomPriorityQueue<Person> personQueue = new CustomPriorityQueue<>(ageComparator);

    personQueue.offer(new Person(30, "Alice"));
    personQueue.offer(new Person(25, "Bob"));
    personQueue.offer(new Person(35, "Charlie"));

    while (!personQueue.isEmpty()) {
        System.out.println(personQueue.poll());
    }
    // 输出顺序：Bob(年龄: 25) → Alice(年龄: 30) → Charlie(年龄: 35)
}

关键注意事项 #

• 类型安全与运行时检查：无参构造器使用时，如果元素未实现Comparable，运行时会抛出ClassCastException，这和Java标准库的行为一致，避免了编译期过度约束，同时保证了运行时的正确性。
• 使用Comparator<? super E>：这里用? super E而不是Comparator<E>是为了支持更灵活的比较器——比如可以用父类的比较器来比较子类元素，提升了代码的复用性。
• 堆结构的选择：示例中用了ArrayList作为存储容器，实际生产环境中，用数组会更高效（因为堆的父/子节点访问是基于索引的，数组的随机访问性能更好），你可以根据需求替换。

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