构建优先队列的线性时间堆化方法-java教程-PHP中文网

构建优先队列的线性时间堆化方法

Java 中通过 PriorityQueue(Collection) 构造器可在线性时间 O(n) 内完成堆化，而逐个 add() 插入则需 O(n log n)；其性能差异源于 heapify() 的自底向上 siftDown 优化与 add() 的自顶向下 siftUp 开销本质不同。

java 中通过 `priorityqueue(collection)` 构造器可在线性时间 o(n) 内完成堆化，而逐个 `add()` 插入则需 o(n log n)；其性能差异源于 `heapify()` 的自底向上 siftdown 优化与 `add()` 的自顶向下 siftup 开销本质不同。

在 Java 中高效构建优先队列（PriorityQueue），关键在于选择正确的初始化方式。常见误区是认为“批量添加”和“构造时传入集合”只是语法糖差异，实则二者时间复杂度存在本质区别：

✅ 推荐方式（O(n)）：
```
PriorityQueue<integer> pq = new PriorityQueue(collection);</integer>
```
此构造器内部调用 heapify() 方法，采用自底向上建堆策略：从最后一个非叶子节点开始，依次执行 siftDown。虽然循环约 n/2 次，但因底层完全二叉树结构的数学特性——平均每个节点下沉距离为常数（≈1），整体比较次数趋近于 ~2n，严格满足线性时间复杂度。
❌ 低效方式（O(n log n)）：
```
PriorityQueue<integer> pq = new PriorityQueue();
pq.addAll(collection); // 或循环调用 pq.add(e)</integer>
```
每次 add() 执行 siftUp，将新元素从叶节点位置上浮至合适位置。最坏情况下需上浮至根节点（深度 ≈ log₂n），n 次插入导致总比较次数约为 n(log₂n − 2)，呈现对数线性增长。

? 实证验证：比较次数对比

以下简化版测试代码（基于原文逻辑）可清晰揭示差异：

// 自定义计数器类（略去完整定义，核心逻辑见原文）
static void benchmark(int n) {
    List<item> items = IntStream.range(0, n)
        .mapToObj(i -> new Item(n - i)) // 逆序构造最坏输入
        .collect(Collectors.toList());

    Counter c1 = new Counter();
    new PriorityQueue(items); // heapify 方式

    Counter c2 = new Counter();
    PriorityQueue<item> pq = new PriorityQueue();
    items.forEach(pq::add); // add 方式

    System.out.printf("%d\t%.2f\t%.2f%n", 
        n, 
        (double) c1.comparisons / n,  // 归一化为 per-element 平均比较数
        (double) c2.comparisons / n);
}</item></item>

运行结果（截取关键规模）显示： | n | heapify 平均比较数 | add 平均比较数 | |---------|-------------------|----------------| | 1023 | ~1.98 | ~8.01 | | 65535 | ~1.9995 | ~14.00 | | 1048575 | ~1.99996 | ~18.00 |

可见：heapify 的单位元素比较数稳定趋近于 2，而 add 方式随 n 增长呈 log₂n 级别上升，验证了理论分析。

⚙️ 底层机制解析

heapify() 核心逻辑（简化）：
```
for (int i = size/2 - 1; i >= 0; i--) {
    siftDown(i, element, queue, size); // 仅处理非叶节点
}
```
因树中约一半节点为叶子（无需调整），且越靠近底部的节点下沉路径越短，加权平均下沉深度为常数。
add() 的 siftUp() 则从末尾插入，每次最多上浮 log₂n 层，且新元素插入位置随机，无结构利用优势。