线性时间构建优先队列：两种实现的性能疑问

先明确两种构建优先级队列的代码实现：

// 方式1：先创建空队列，再批量添加元素
PriorityQueue<Integer> pq = new PriorityQueue<>();  
pq.addAll(collection);  

// 方式2：直接传入集合构造队列
PriorityQueue<Integer> pq = new PriorityQueue<>(collection);

理论时间复杂度差异 #

• 方式1：addAll会遍历集合逐个调用add方法，每次添加都会执行siftUp操作——把新元素上浮到堆中合适的位置。每次siftUp的最坏时间复杂度是O(logk)（k为当前堆的大小），累加下来总时间复杂度是O(n logn)（n为集合元素总数）。
• 方式2：当传入普通集合时，构造方法会先把元素全部复制到内部数组，再调用heapify()方法完成堆构建。heapify从最后一个非叶子节点开始，逐个执行siftDown操作，经典堆构建的时间复杂度是O(n)，理论上比方式1高效。

为什么小数据量测试看不到性能差异？ #

你怀疑数据量过小是核心原因，这个判断是对的，除此之外还有几个关键因素：

1. JVM基础开销掩盖差异：小数据量下，对象创建、方法调用、内存分配的开销远大于堆调整的耗时。比如当n只有几千时，O(n)和O(n logn)的绝对时间差可能只有几微秒，被JVM的其他操作（比如GC、方法栈切换）完全掩盖。
2. 自定义比较器的耗时占比：如果你的自定义对象比较逻辑本身比较复杂，比较操作的时间会远超过堆调整的时间，两种构建方式的性能差异会被比较逻辑的耗时淹没。
3. JIT编译的延迟优化：JVM的即时编译（JIT）需要一定的执行次数才会触发，小数据量测试可能还没进入JIT优化阶段，两种方式的执行效率都处于解释执行的水平，差异不明显。
4. 输入集合的有序性影响：如果你的测试集合本身已经接近堆的有序状态，方式1的siftUp操作几乎不需要移动元素，实际耗时会接近O(n)，和方式2的heapify差异自然很小。但如果用完全逆序的集合测试（比如用降序数组构建小顶堆），方式1的耗时会陡增，此时即使数据量中等（比如十万级）也能看到明显差异。

如何验证性能差异？ #

可以尝试以下测试方案：

• 用百万级以上的随机元素集合（避免有序性干扰），分别统计两种方式的耗时，取多次测试的平均值。
• 用逆序排列的集合（比如降序整数数组）构建小顶堆，放大两种方式的时间差异。
• 简化自定义比较器的逻辑（比如只比较单个整数字段），减少比较操作对性能测试的干扰。

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