构建优先队列的线性时间方法：heapify 优于逐个插入-java教程-PHP中文网

构建优先队列的线性时间方法：heapify 优于逐个插入

Java 中通过 new PriorityQueue(collection) 构造优先队列可实现 O(n) 时间复杂度的堆化（heapify），而逐个 add() 插入则需 O(n log n)；其本质差异源于 siftDown（自上而下调整）的平均常数时间开销 vs siftUp（自下而上上浮）的对数级路径长度。

java 中通过 `new priorityqueue(collection)` 构造优先队列可实现 o(n) 时间复杂度的堆化（heapify），而逐个 `add()` 插入则需 o(n log n)；其本质差异源于 siftdown（自上而下调整）的平均常数时间开销 vs siftup（自下而上上浮）的对数级路径长度。

在 Java 中高效构建优先队列（即最小堆或最大堆），关键在于理解底层堆化（heapify）机制的时间复杂度差异。虽然两种常见写法表面相似，但性能表现截然不同：

// ✅ O(n)：一次性构造，触发 heapify
PriorityQueue<integer> pq1 = new PriorityQueue(collection);

// ❌ O(n log n)：逐个插入，每次调用 siftUp
PriorityQueue<integer> pq2 = new PriorityQueue();
pq2.addAll(collection); // 等价于 for (e : collection) pq2.add(e);</integer></integer>

为什么 heapify 是线性的？

PriorityQueue 的带集合参数构造器内部调用私有方法 heapify()，其核心逻辑是从最后一个非叶子节点（索引为 n/2 - 1）开始，自底向上执行 siftDown：

private void heapify() {
    final Object[] es = queue;
    int n = size, i = (n >>> 1) - 1; // 从最后一个非叶节点开始
    if (comparator == null) {
        for (; i >= 0; i--)
            siftDownComparable(i, (E) es[i], es, n); // 关键：仅需 n/2 次 siftDown
    } else { /* ... */ }
}

乍看之下，n/2 次 siftDown、每次最坏 O(log n)，似乎仍是 O(n log n)。但堆的完全二叉树结构决定了平均下潜深度仅为常数。

在高度为 h = ⌊log₂n⌋ 的满二叉堆中：
- 第 h 层（叶子层）有 2^h ≈ n/2 个节点，下潜距离为 0；
- 第 h−1 层有 2^{h−1} 个节点，最大下潜距离为 1；
- 第 0 层（根）仅 1 个节点，最大下潜距离为 h。

总比较次数上限可估算为：

Σ (层数 k) × (该层节点数) × (最大下潜步数)
= Σ_{k=0}^{h−1} 2^k × (h − k) = 2^h × Σ_{j=1}^h j / 2^j <p>数学推导表明：<strong>平均下潜距离收敛于常数（≈1）</strong>，因此 heapify 整体为 <strong>O(n)</strong>。</p><h3>为什么 addAll() 是 O(n log n)？</h3><p>addAll() 实质是 n 次 add() 调用，每次执行 siftUp —— 从叶子位置<strong>向上浮至合适位置</strong>：</p><pre class="brush:php;toolbar:false;">private void siftUp(int k, E x) {
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        if (key.compareTo((T) es[parent]) >= 0) break;
        es[k] = es[parent];
        k = parent;
    }
    es[k] = key;
}

最坏情况下（如逆序插入），每个新元素都需上浮至根，路径长度达 O(log n)。n 次操作累加即为 O(n log n)。实测数据也印证了这一规律：