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);</integer></integer>
但其时间复杂度存在本质差异——方式 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 {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 <p>运行结果（归一化至每元素平均比较次数）显示：</p>
<table>
<thead><tr>
<th>n</th>
<th>heapify (per item)</th>
<th>add() (per item)</th>
</tr></thead>
<tbody>
<tr>
<td>1,023</td>
<td>~1.98</td>
<td>~8.01</td>
</tr>
<tr>
<td>65,535</td>
<td>~1.9995</td>
<td>~14.00</td>
</tr>
<tr>
<td>1,048,575</td>
<td>~1.99996</td>
<td>~18.00</td>
</tr>
</tbody>
</table>
<p>可见：heapify 的单位开销稳定在 <strong>≈2 次比较</strong>，而 add() 则随 log₂n 线性增长。</p>
<h3>注意事项与最佳实践</h3>
<ul>
<li>✅ <strong>优先使用构造器初始化</strong>：只要初始数据已知，一律选用 new PriorityQueue(collection)。</li>
<li>⚠️ <strong>自定义 Comparator 同样适用</strong>：PriorityQueue(Collection, Comparator) 会调用相同 heapify() 流程，复杂度不变。</li>
<li>⚠️ <strong>小数据量下差异不明显</strong>：当 n </li>
<li>❌ 避免误用 addAll()：它本质是循环调用 add()，无法触发 heapify 优化。</li>
<li>? 若需动态增量构建（流式数据），则 add() 不可避免，此时应接受 O(n log n) 开销。</li>
</ul>
<p>综上，理解堆的结构性质（叶节点占比高、平均下沉距离短）是掌握线性建堆的关键。在工程实践中，一个简单的构造器选择，即可在大数据场景下带来数倍性能提升——这正是算法底层洞见赋能高效编程的典型范例。</p></counter.item></counter.item></item>
