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

本文共计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)

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

有人误以为插入也会触发下沉，其实不会。