在优先级堆中，如何实现插入新变量后节点的深度追踪与调整？

本文共计682个文字，预计阅读时间需要3分钟。

`PriorityQueue` 插入新元素时，底层堆结构会通过 `上浮（sift-up）` 操作维护堆序；删除堆顶元素时，才触发 `下沉（sift-down）`。上浮是确保新元素从尾部冒泡到正确位置，保证堆序；下沉则是在删除堆顶元素后，调整剩余元素，恢复堆的性质。

上浮怎么发生：从插入位置开始逐层比对父节点

新元素总被追加到数组末尾（逻辑上的完全二叉树最右下叶子位置）。此时只需沿父节点链向上比较：

• 计算当前索引 i 的父节点索引：(i − 1) // 2
• 若为大根堆，且当前值 > 父值，则交换；否则停止
• 更新索引为父索引，重复比较，直到到达根（索引 0）或不再满足上浮条件

为什么不用从头建堆：单次插入只需 O(log n) 时间

插入不重排整个数组，只影响从叶到根的一条路径。例如向已有 15 个元素的大根堆插入新值：

• 新元素放在索引 15（第 16 位），父节点在索引 7
• 最多比较 4 次（因 log₂16 = 4），就能确定最终位置
• 时间复杂度稳定为 O(log n)，远优于重新建堆的 O(n)

下沉不在插入阶段出现：它是删除堆顶时的配套动作

有人误以为插入也会触发下沉，其实不会。下沉用于删除后填补空缺：把最后一个元素挪到堆顶，再让它“沉”到合适位置。插入过程只涉及向上调整，因为只有新节点可能破坏“父 ≥ 子”（大根堆）这一局部关系，且破坏只可能出现在其祖先路径上。

Java 中的 PriorityQueue 默认行为细节

默认构造的 PriorityQueue<Integer> 是小根堆（最小优先）：

• 插入 5、3、8、1 后，内部数组逻辑顺序可能是 [1, 3, 8, 5]（不保证全有序，但满足堆结构）
• 调用 poll() 取出 1，此时将末尾 5 移至堆顶，再下沉调整 → 新堆为 [3, 5, 8]
• 上浮与下沉均由 JDK 内部私有方法如 siftUpComparable 和 siftDownComparable 实现，用户不可见但可依赖其正确性