如何使用Collection与自定义Comparator高效构造Java PriorityQueue

原生 JDK 8 及更早版本的 PriorityQueue 确实没有公开的同时传入集合和自定义比较器的构造方法，我们可以根据运行环境选择以下方案实现 O(n) 时间复杂度的带自定义比较器堆化：

方案1：Java 9+ 直接使用官方新增构造方法 #

Java 9 开始官方已经新增了对应的构造函数 PriorityQueue(Comparator<? super E> comparator, Collection<? extends E> c)，内部直接基于传入的比较器做 O(n) 堆化，无需额外处理：

List<Integer> list = Arrays.asList(5,4,5,2,2);
// 直接传入比较器和集合，时间复杂度O(n)
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder(), list);

方案2：Java 8 及更低版本兼容实现（反射方案） #

如果必须兼容 Java 8 及更早版本，可以通过反射调用 PriorityQueue 的内部堆化方法实现，该方案依赖 JDK 内部实现，建议在可控的内部项目中使用：

import java.lang.reflect.Field;
import java.lang.reflect.Method;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

public class CustomHeapBuilder {
    public static <E> PriorityQueue<E> build(List<E> elements, java.util.Comparator<? super E> comparator) throws Exception {
        int elementCount = elements.size();
        // 初始化带自定义比较器、容量匹配的空队列
        PriorityQueue<E> heap = new PriorityQueue<>(elementCount, comparator);

        // 写入元素到内部存储数组
        Field queueField = PriorityQueue.class.getDeclaredField("queue");
        queueField.setAccessible(true);
        Object[] internalQueue = (Object[]) queueField.get(heap);
        elements.toArray(internalQueue);

        // 更新队列元素计数
        Field sizeField = PriorityQueue.class.getDeclaredField("size");
        sizeField.setAccessible(true);
        sizeField.setInt(heap, elementCount);

        // 调用内部heapify方法完成O(n)堆化
        Method heapifyMethod = PriorityQueue.class.getDeclaredMethod("heapify");
        heapifyMethod.setAccessible(true);
        heapifyMethod.invoke(heap);

        return heap;
    }

    public static void main(String[] args) throws Exception {
        List<Integer> list = Arrays.asList(5,4,5,2,2);
        PriorityQueue<Integer> maxHeap = build(list, Collections.reverseOrder());
        // 输出堆顶元素为5，验证最大堆构造成功
        System.out.println(maxHeap.peek());
    }
}

方案3：无反射纯公开API实现 #

如果不想依赖反射和高版本JDK，可以自行实现标准的O(n)堆化逻辑，将集合转为数组后用自定义比较器完成堆化，再将堆化后的数组逐个赋值给空的PriorityQueue即可，逻辑和JDK内部的heapify完全一致，不会出现兼容性问题，时间复杂度依然是O(n)。

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