Java 中通过 new PriorityQueue<>(collection) 构造器可在线性时间 O(n) 内完成堆化，而逐个 add() 插入则需 O(n log n)，二者性能差异在数据规模增大时显著显现。
java 中通过 `new priorityqueue(collection)` 构造器可在线性时间 o(n) 内完成堆化，而逐个 `add()` 插入则需 o(n log n)，二者性能差异在数据规模增大时显著显现。
在 Java 中高效构建优先队列（PriorityQueue）的关键，在于理解底层二叉堆的初始化策略。虽然两种常见写法看似等价：
// 方式 1：逐个添加 → O(n log n) PriorityQueue<Integer> pq1 = new PriorityQueue<>(); pq1.addAll(collection); // 方式 2：构造器直接传入集合 → O(n) PriorityQueue<Integer> pq2 = new PriorityQueue<>(collection);
但其时间复杂度存在本质差异——方式 2 调用的是 heapify() 算法，可在 O(n) 时间内完成自底向上建堆；而方式 1 实质是 n 次 offer() 操作，每次 siftUp 最坏耗时 O(log n)，总时间为 O(n log n)。
为什么 heapify() 是线性的？
heapify() 的核心逻辑是从最后一个非叶子节点（索引为 n/2 - 1）开始，逆序执行 siftDown。乍看之下，n/2 次 siftDown、每次最多 O(log n)，似乎应为 O(n log n)。但关键在于平均分析：
- 在完全二叉树中，约一半节点位于最底层（叶节点），它们无需下沉；
- 倒数第二层节点最多下沉 1 层，数量约为 n/4；
- 倒数第三层最多下沉 2 层，数量约为 n/8；
- …依此类推。
总比较次数上限为： $$ \sum_{h=0}^{\lfloor \log2 n \rfloor} \frac{n}{2^{h+1}} \cdot h < n \sum{h=0}^\infty \frac{h}{2^{h+1}} = n $$ 该级数收敛于常数（实际约为 2），因此 heapify() 的平均比较次数 ≈ 2n，属严格线性。
相比之下，add() 使用 siftUp：新元素从末尾插入，逐层与父节点比较并上浮，最坏需抵达根节点（log₂n 层）。n 个元素依次插入，总比较次数趋近于： $$ \sum_{i=1}^{n} \lfloor \log_2 i \rfloor \approx n(\log_2 n - 2) $$ 即 O(n log n) —— 这正是实测中随规模增长而迅速拉开差距的根本原因。
实测验证（关键洞察）
以下精简版测试代码通过计数比较操作，清晰揭示渐进差异：
static class Counter {
int comparisons = 0;
class Item implements Comparable<Item> {
final int value;
Item(int v) { this.value = v; }
public int compareTo(Item o) { comparisons++; return Integer.compare(value, o.value); }
}
}
public static void benchmark(int n) {
Counter c1 = new Counter();
List<Counter.Item> list = IntStream.range(0, n)
.mapToObj(i -> c1.new Item(n - i)).collect(Collectors.toList());
new PriorityQueue<>(list); // heapify: ~2n comparisons
Counter c2 = new Counter();
PriorityQueue<Counter.Item> pq = new PriorityQueue<>();
for (int i = 0; i < n; i++) {
pq.add(c2.new Item(n - i)); // n × siftUp: ~n(log₂n − 2)
}
System.out.printf("%d\t%.3f\t%.3f%n",
n, (double)c1.comparisons/n, (double)c2.comparisons/n);
}运行结果（归一化至每元素平均比较次数）显示：
| n | heapify (per item) | add() (per item) |
|---|---|---|
| 1,023 | ~1.98 | ~8.01 |
| 65,535 | ~1.9995 | ~14.00 |
| 1,048,575 | ~1.99996 | ~18.00 |
可见：heapify 的单位开销稳定在 ≈2 次比较，而 add() 则随 log₂n 线性增长。
注意事项与最佳实践
- ✅ 优先使用构造器初始化：只要初始数据已知，一律选用 new PriorityQueue<>(collection)。
- ⚠️ 自定义 Comparator 同样适用：PriorityQueue(Collection, Comparator) 会调用相同 heapify() 流程，复杂度不变。
- ⚠️ 小数据量下差异不明显：当 n < 1000 时，常数因子主导，实测可能难察觉；务必在 n ≥ 10⁴ 量级验证。
- ❌ 避免误用 addAll()：它本质是循环调用 add()，无法触发 heapify 优化。
- ? 若需动态增量构建（流式数据），则 add() 不可避免，此时应接受 O(n log n) 开销。
综上，理解堆的结构性质（叶节点占比高、平均下沉距离短）是掌握线性建堆的关键。在工程实践中，一个简单的构造器选择，即可在大数据场景下带来数倍性能提升——这正是算法底层洞见赋能高效编程的典型范例。
