Java Priority Queue能否实现O(n)时间复杂度的高效建堆？

Java PriorityQueue完全可以实现*O(n)时间复杂度的建堆效率，哪怕需要使用自定义比较器、对自定义类对象排序，也不存在“只能逐元素入队、达到O(nlogn)*复杂度”的限制，之前的认知误区主要来自对构造器、底层实现逻辑的不熟悉。

PriorityQueue的两类入堆操作的效率有本质区别：

• 逐元素offer/add单个元素：每加入一个元素就从树的尾部做siftUp向上调整，整体累计时间复杂度是O(nlogn)，也就是循环逐个入队时的低效模式。
• 批量heapify：把所有待入堆元素先一次性存入内部数组，再从最后一个非叶子节点开始反向做siftDown向下调整，整体时间复杂度就是理论上的*O(n)*建堆效率，和new PriorityQueue<>(list)这类直接传集合的构造器底层逻辑完全一致。

JDK9及以上版本：空队列下的addAll批量优化 #

JDK9开始PriorityQueue重写了addAll方法：当队列为空（即size=0）时，不会走逐元素入队的逻辑，而是直接把传入集合的元素拷贝到内部数组，完成后直接调用heapify做整体调整，这个过程和构造器批量建堆的效率没有任何区别，也完全适配带重复元素、自定义类对象排序的场景，没有副作用。
对应的大顶堆正确写法：

List<Integer> list = new ArrayList<>(Arrays.asList(5,6,7,0,1,33));
// 第一步：先初始化队列，绑定自定义比较器
Queue<Integer> queue = new PriorityQueue<>((a, b) -> b.compareTo(a));
// 第二步：空队列状态下批量入堆，触发O(n)建堆
queue.addAll(list);

JDK8及更早版本：借助SortedSet中转 #

JDK8及更早的版本没有上述addAll的批量优化，但可以利用PriorityQueue集合构造器的内置逻辑触发*O(n)*建堆：
当调用new PriorityQueue<>(c)时，如果传入的集合是SortedSet类型，构造器会自动提取SortedSet内置的比较器，再把SortedSet的元素拷贝到内部数组后直接走heapify调整流程。
对应的实现写法：

List<Integer> list = new ArrayList<>(Arrays.asList(5,6,7,0,1,33));
// 用带自定义比较器的TreeSet中转，触发构造器的批量建堆逻辑
Queue<Integer> queue = new PriorityQueue<>(new TreeSet<>((a, b) -> b.compareTo(a)) {{
    addAll(list);
}});

注意：这种方式存在局限——TreeSet会自动对元素去重，如果待入堆的列表存在重复元素，会出现数据丢失，仅适合无重复元素的场景。

• 不存在“没有同时接收初始集合和自定义比较器的构造方法，就没法用*O(n)*建堆”的问题：构造器只是代码入口，只要能让队列的比较器正确绑定、最终走到heapify逻辑，就能达到理论上的建堆效率。
• 建堆的时间复杂度和是否使用自定义比较器无关：不管是自然排序还是自定义逻辑，批量建堆的整体调整次数是固定的，比较器只影响单次比较的执行逻辑，不会改变*O(n)*的时间复杂度量级。
• 逐元素入队的写法不是实现大顶堆的唯一方式：这种*O(nlogn)*的写法只是大家图方便凑出来的临时实现，完全可以通过上述路径实现和理论值一致的建堆效率。

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