11.2　上浮与下沉

学习目标：学完本节，你能

手写上浮和下沉，并说清各自用在什么时机；
解释"插入为什么必须放在末尾""删除根为什么要用末尾元素顶替"；
说出下沉为什么比上浮稍贵，以及这个差异带来的后果。

先修：11.1（堆的定义与数组表示）、8.3（下沉与建堆）。 固定术语：上浮、下沉、堆序恢复。 环境与版本：.NET 8 / C# 12。 预计阅读：28 分钟。

本节用【小顶堆】（父 ≤ 子），配合优先队列的场景。8.3 节的堆排序用的是【大顶堆】—— 方向相反，逻辑完全对称。

一、直觉：两个方向相反的"调整"

堆的破坏只会来自两个地方，而修复它们需要两个方向相反的操作：

操作	何时用	方向	修复什么问题
上浮（Sift Up）	插入新元素后	往上（朝根）	新元素可能比祖先小
下沉（Sift Down）	删除根之后 / 建堆时	往下（朝叶）	顶上来的元素可能比后代大

一句话概括：

上浮是"小的往上冒"，下沉是"大的往下沉"。

两者都沿着一条从根到叶的路径走，所以复杂度都是 $O(\log n)$（树高）。

二、上浮：插入时用

/// <summary>
/// 上浮：把下标 i 的元素往上调整，直到它的父节点不大于它。
/// 【用在插入时】—— 新元素放在末尾，然后一路上浮找位置。
/// </summary>
static void SiftUp(int[] a, int i, ref long cmp, ref long swaps, bool trace = false)
{
    while (i > 0)
    {
        int parent = (i - 1) / 2;      // 父节点下标
        cmp++;

        if (a[parent] <= a[i]) break;  // 父节点已经不大于自己了，停

        (a[parent], a[i]) = (a[i], a[parent]);
        swaps++;
        i = parent;                    // 继续往上检查
    }
}

实测：往 [2, 5, 3, 8, 7, 6] 里插入 1（比所有元素都小）

  初始堆: [2, 5, 3, 8, 7, 6]
  对应的树：
          2
       /     \
      5       3
     / \     /
    8   7   6

  先放到末尾 -> [2, 5, 3, 8, 7, 6, 1]

      比较 a[6]=1 和父 a[2]=3
        交换 -> [2, 5, 1, 8, 7, 6, 3]
      比较 a[2]=1 和父 a[0]=2
        交换 -> [1, 5, 2, 8, 7, 6, 3]

  上浮完成: [1, 5, 2, 8, 7, 6, 3]
  比较 2 次，交换 2 次

新的树：

          1
       /     \
      5       2
     / \     / \
    8   7   6   3

1 一路从最底部浮到了根 —— 因为它比沿途所有祖先都小。

注意上浮的路径：1 只走了 下标 6 → 2 → 0 这一条路，完全没有碰其他分支。

这就是"只沿一条路径"的含义 —— 也是 $O(\log n)$ 的来源。

三、下沉：删除根时用

/// <summary>
/// 下沉：把下标 i 的元素往下调整，直到它不大于它的两个孩子。
/// 【用在删除根时，以及建堆时】。
/// </summary>
static void SiftDown(int[] a, int i, int size, ref long cmp, ref long swaps, bool trace = false)
{
    while (true)
    {
        int smallest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < size)
        {
            cmp++;
            if (a[left] < a[smallest]) smallest = left;    // 左孩子更小？记下来
        }
        if (right < size)
        {
            cmp++;
            if (a[right] < a[smallest]) smallest = right;  // 右孩子更小？记下来
        }

        if (smallest == i) break;      // 两个孩子都不比自己小，停

        (a[i], a[smallest]) = (a[smallest], a[i]);
        swaps++;
        i = smallest;
    }
}

注意：size 参数是堆的有效范围 —— 堆排序时堆会不断缩小（8.3 节）。

实测：取走根（最小值 1）

  当前堆: [1, 5, 2, 8, 7, 6, 3]
  取走根（最小值 1）

  第 1 步：把末尾的 3 移到根的位置
          -> [3, 5, 2, 8, 7, 6]

  第 2 步：对根执行下沉
      最小的是 a[2]=2，交换
        交换 -> [2, 5, 3, 8, 7, 6]
        两个孩子都不比它小，停在这里

结果 [2, 5, 3, 8, 7, 6] —— 又是一个合法的小顶堆 ✓

验证：根是 2（新的最小值）✓；下标 0 的孩子是 5 和 3，都 ≥ 2 ✓；下标 1 的孩子是 8、7，都 ≥ 5 ✓

四、两个"为什么"

为什么插入必须放在末尾？

有人会想：插入 1 的时候，为什么不直接把它放到根上？

实测这个"错误做法"：

  错误做法（直接插到根，其他元素整体后移）:
    [1, 2, 5, 3, 8, 7, 6]

看起来数组确实变"有序"了一点，但它不再是一棵合法的完全二叉树了。

  原来的树：根 2，左 5，右 3，5 的孩子是 8、7，3 的孩子是 6

  整体后移后，节点之间的父子关系全变了！
  比如下标 1 的 2，它的孩子变成了下标 3 的 5 和下标 4 的 3 ——
  但原来是 2 的孩子是 5 和 3，现在 5 和 3 变成了 2 的孙子辈。

根本原因：数组表示依赖"层序编号与下标一一对应"这个前提（11.1 节）。

只要在中间插入元素，后面所有元素的下标都会位移，父子关系全部错乱。

所以插入必须放在末尾 —— 那是保持"完全二叉树"的唯一位置。放好之后再靠上浮调整，既不破坏结构，代价也只有 $O(\log n)$。

为什么删除根要用末尾元素顶替？

同理：直接删掉根会在树的【顶部】留一个空洞。

  直接删根:              用末尾顶替:
        2                      3          <- 末尾的 3 移上来
      /   \                  /   \
     5     3    -->         5     2       <- 形状仍然合法
    / \   /                 / \
   8   7 6                 8   7 6
        ↑
     这里空了

"末尾元素顶替 + 下沉"这个组合同时解决了两件事：

保持"完全"：长度减一，剩下的元素仍然连续排列 ✓
只需要一次下沉就能恢复堆序 ✓

这和 8.3 节堆排序的做法本质相同 —— 那里是"把根和最末尾交换"（因为要保留被换出去的元素用于排序），这里是"直接覆盖"（因为被删的元素就是不要的）。

五、上浮 vs 下沉：一个不对称的细节

  维度               | 上浮 SiftUp              | 下沉 SiftDown
  --------------------------------------------------------------------------
  移动方向            | 往上（朝根）              | 往下（朝叶）
  用在什么时候         | 插入新元素后              | 删除根之后 / 建堆时
  和谁比较            | 只和【一个】父节点比        | 和【两个孩子】比
  每次比较的代价       | 1 次比较                 | 最多 2 次比较
  最多走几层          | 树高 = log n             | 树高 = log n

注意一个不对称的地方：

上浮时，每个节点只有一个父节点 —— 比较 1 次就知道该不该继续。

下沉时，每个节点有两个孩子 —— 要先找出"较小的那个孩子"，再决定要不要交换。

所以下沉比上浮稍贵。

这个差异带来一个重要后果：

建堆要用【下沉】，而不是"逐个插入用上浮"。

逐个插入（n 次上浮）：每次 $O(\log n)$，总共 $O(n \log n)$

自底向上建堆（用下沉）：大部分节点在底层，下沉距离很短，总共只要 $O(n)$

虽然下沉单次更贵，但用在正确的地方，总代价反而更低。（8.3 节用级数收敛证明了 $O(n)$）

这个"单次更贵但总量更省"的现象，在算法里很常见 —— 比如 3.2 节动态数组的扩容（单次 $O(n)$，摊还 $O(1)$）。

六、验证：用一组随机操作测一下

插 200 个随机数进去，再逐个取出最小值，看取出序列是否升序：

  插入 200 个随机数，再逐个取出最小值
  取出的序列是升序吗？True
  前 10 个取出的值: 2 3 3 8 9 12 12 13 19 24
  累计比较 2,510 次，交换 1,238 次

取出序列是升序的 ✓ —— 这说明堆的两个操作配合起来是对的。

量级核对：400 次操作（200 插入 + 200 取出）× 平均约 6 次比较 ≈ 2,400 次 —— 实测 2,510 次，吻合。

这就是"优先队列"的核心：不断插入、不断取最小值，每次都是 $O(\log n)$。

下一节会把它封装成一个完整的类。

七、练习

练习 11.2.1（手写推演）堆 [3, 8, 5, 10, 9, 7]（小顶堆）。 (a) 插入 1，写出上浮的每一步。 (b) 在 (a) 的结果上，取走最小值，写出下沉的每一步。

练习 11.2.2（代码阅读）下面这个 SiftUp 有一个 bug，请指出：

static void SiftUp(int[] a, int i)
{
    while (i > 0)
    {
        int parent = (i - 1) / 2;
        if (a[parent] <= a[i]) break;
        (a[parent], a[i]) = (a[i], a[parent]);
        // 缺少一行
    }
}

练习 11.2.3（判断）判断对错并说明理由： (a) 上浮和下沉的复杂度都是 $O(\log n)$，因为它们都只走一条路径。 (b) 插入新元素时，也可以放在数组开头，然后下沉。 (c) 下沉每次最多比较 2 次，所以下沉比上浮快。

练习 11.2.4（工程判断）一个优先队列的插入操作很频繁（每秒 10 万次），但取最小值很少（每秒 10 次）。 (a) 插入和取出的复杂度各是多少？ (b) 总代价主要花在哪一边？ (c) 有没有可能优化？提示：想想能不能"攒一批再处理"。

练习 11.2.5（挑战·从任意位置删除）堆只支持"删除根"，但实际业务可能需要"删除任意一个元素"（比如取消一个已排队的任务）。 (a) 想一下：如果知道要删元素的下标，怎么删？ (b) 删完之后，应该上浮还是下沉？ (c) 有没有办法做到 $O(\log n)$？

八、练习答案

11.2.1

堆 [3, 8, 5, 10, 9, 7]：

(a) 插入 1：

第 1 步：放到末尾 → [3, 8, 5, 10, 9, 7, 1]（下标 6）

第 2 步：上浮

步骤	当前位置	值	父节点	父值	比较	动作
1	下标 6	1	下标 2	5	$5 > 1$	交换 → `[3, 8, 1, 10, 9, 7, 5]`
2	下标 2	1	下标 0	3	$3 > 1$	交换 → `[1, 8, 3, 10, 9, 7, 5]`
3	下标 0	1	—	—	到根了	停

结果：[1, 8, 3, 10, 9, 7, 5]

验证：根是 1；下标 0 的孩子 8、3 都 ≥ 1 ✓；下标 1 的孩子 10、9 都 ≥ 8 ✓；下标 2 的孩子 7 ≥ 3 ✓

(b) 取走最小值 1：

第 1 步：末尾元素移到根 → 末尾是 5，移到根 → [5, 8, 3, 10, 9, 7]

第 2 步：下沉

步骤	当前位置	值	左孩子	右孩子	最小的	动作
1	下标 0	5	下标 1 = 8	下标 2 = 3	3（下标 2）	交换 → `[3, 8, 5, 10, 9, 7]`
2	下标 2	5	下标 5 = 7	无	5 自己	停

结果：[3, 8, 5, 10, 9, 7] —— 正好回到初始状态 ✓

有意思的是：插入 1 再取走 1，堆回到了原样。这说明两个操作是互逆的（在不考虑具体元素的情况下）。

11.2.2

缺少了 i = parent; 这一行。

static void SiftUp(int[] a, int i)
{
    while (i > 0)
    {
        int parent = (i - 1) / 2;
        if (a[parent] <= a[i]) break;
        (a[parent], a[i]) = (a[i], a[parent]);
        i = parent;      // ← 缺这一行！必须往上走，否则会无限循环
    }
}

后果：i 永远不变，循环会无限执行 —— 每轮都把同一个元素和它的父节点交换一次，然后再交换回来，死循环。

这类 bug 的特点：程序不会崩，也不会报错，就是卡住了（CPU 100%）。

写循环版的树操作时，"指针有没有前进"是最需要检查的地方 —— 和 3.4 节滑动窗口里"left 只增不减"是同一类关注点。

11.2.3

(a) 对。 上浮只沿着"当前节点 → 父 → 祖父 → … → 根"这一条链走；下沉只沿着"当前节点 → 较小/较大的孩子 → … → 叶子"这一条链走。

两者最多走"树高"步，而堆是完全二叉树，树高是 $O(\log n)$。
(b) 错。 放在数组开头 = 放在根的位置 —— 这会让原来的根和它的位置关系全部错乱（见本节第四节的实测）。

数组表示依赖"层序编号与下标一一对应"。在任何非末尾位置插入，都会让后面的元素下标位移，父子关系全部失效。
(c) 错，方向反了。 下沉每次要在两个孩子里找最小的（最多 2 次比较），而上浮只需要和一个父节点比（1 次比较）。

所以下沉比上浮【更贵】。

本节第五节的表里专门标出了这个不对称 —— 它的后果是"建堆要用下沉而不是逐个插入"。

11.2.4

(a) 两者都是 $O(\log n)$。

假设队列里平均有 10 万个元素，$\log_2(100{,}000) \approx 17$：

插入：约 17 次比较/交换
取出：约 17 × 2 = 34 次比较（因为每层要比两个孩子）

(b) 总代价：

插入：10 万次/秒 × 17 = 170 万次操作/秒
取出：10 次/秒 × 34 = 340 次操作/秒

代价几乎全在插入这一边（相差 5000 倍）。

(c) 可以优化 —— 但要看业务能不能接受"批量延迟"。

思路：把插入缓冲起来，批量处理。

方案：维护两个容器
  - 一个【无序的缓冲区】（比如 List），新元素直接追加，O(1)
  - 一个【堆】，保存已经整理过的元素

取最小值时：
  1. 如果缓冲区非空，把它里面的元素全部倒进堆（一次 O(k + k log n)）
  2. 从堆里取根

效果：

插入从 $O(\log n)$ 降到 $O(1)$（只是追加到一个列表）
取出时如果正好赶上"倒数据"，会贵一些（但那 10 次/秒的频率完全可以承受）

这笔交易成立的前提是"插多取少" —— 正好符合题目的场景。

这也是很多"批量处理"优化的通用思路：把贵操作的代价攒起来，在便宜的那一侧一次性支付。

注意：这个方案会引入延迟 —— 刚插入的元素不会立刻出现在堆里，直到下一次"倒数据"。如果业务要求"插入后立刻能被取出"，这个方案就不能用。

11.2.5

(a) 删除任意下标的元素：

1. 把这个位置的元素替换成【数组末尾的元素】
2. 删除末尾（长度减 1）
3. 对刚才那个位置执行调整

为什么用末尾元素顶替？ 和"删除根"是同一个理由 —— 保持完全二叉树的结构（不能在中间留空洞）。

(b) 两种情况都可能，取决于"顶替上来的元素"和周围元素的大小关系：

情况	用什么
顶替元素比父节点小	上浮
顶替元素比孩子大	下沉

简单可靠的做法：两个都试 —— 先上浮，如果没动过，再下沉。

static void RemoveAt(int[] a, int i, int size)
{
    a[i] = a[size - 1];          // 末尾顶替
    // 尝试上浮（如果新元素比父小，它会上浮）
    SiftUp(a, i);
    // 再尝试下沉（如果上浮没动，说明它 >= 父，那可能需要下沉）
    SiftDown(a, i, size - 1);
}

注意：两个操作里最多只有一个会真正移动元素。

如果新元素比父小 → 上浮会动它，之后它一定 >= 新的父，下沉不会再动

如果新元素 >= 父 → 上浮立即停止，下沉负责把它放到该去的位置

所以两个都调用的总代价仍然是 $O(\log n)$（而不是 $2\log n$ 的常数问题 —— 因为只有一条路径会真正走完）。

(c) 能做到 $O(\log n)$ —— 但前提是"能从元素快速找到它的下标"。

难点在于：如果只给"要删除的元素值"，你不知道它在数组里的哪个下标 —— 需要先查找，而堆是无序的，查找是 $O(n)$。

解法：额外维护一个"元素 → 下标"的哈希表，并且在下沉/上浮的每次交换时同步更新它。

// 每次交换 a[i] 和 a[j] 时：
(positionMap[a[i]], positionMap[a[j]]) = (i, j);

这样：

查找元素下标：$O(1)$（查哈希表）
删除并调整：$O(\log n)$

总代价 $O(\log n)$ ✓

代价是：

额外 $O(n)$ 的内存（那个哈希表）

每次交换多两行代码（同步哈希表）—— 常数变大

实现复杂度明显上升，而且极易漏掉某次交换导致哈希表失效

这就是典型的"用空间和复杂度换性能"。

工程上的判断：如果"删除任意元素"是高频操作，值得做这个优化；如果只是偶尔调用（比如"取消任务"一天几百次），直接 $O(n)$ 查找 + $O(\log n)$ 删除更简单、更不容易出错。

.NET 的 PriorityQueue 提供了 Remove 方法 —— 它内部就是用了类似的技巧。

九、常见错误

误区	纠正
上浮/下沉时忘记"指针前进"	会无限循环（不崩不报错，就是 CPU 卡死）。练习 11.2.2 就是这个 bug。
插入时放到非末尾位置	会破坏"完全二叉树"的数组表示，父子关系全乱。必须放末尾再上浮。
删根时直接删掉	会在顶部留空洞。要用末尾元素顶替，再下沉。
认为"下沉比上浮快"	方向反了。下沉每层要比两个孩子，比上浮贵。
建堆用"逐个插入"	那是 $O(n \log n)$。自底向上建堆用下沉，只要 $O(n)$（8.3 节）。
大顶堆和小顶堆的下沉写混	大顶堆找最大的孩子，小顶堆找最小的孩子。符号方向必须和堆序一致。

十、本节总结

两个方向相反的操作：上浮（插入后用，往上找位置）、下沉（删根/建堆时用，往下找位置）。
插入必须放末尾：放在任何其他位置都会破坏"层序编号 ↔ 数组下标"的对应关系。实测演示了错误做法。
删根必须用末尾元素顶替：直接删会在顶部留空洞，破坏完全二叉树的性质。
两个都是 $O(\log n)$：因为它们都只沿着一条从根到叶的路径走。
下沉比上浮贵（每层要比两个孩子 vs 一个父节点）—— 但这个差异换来的是"建堆能做到 $O(n)$"。
实测验证：插 200 个、取 200 个，取出序列升序 ✓，比较 2,510 次（与理论量级吻合）。
删除任意元素：末尾顶替 + 上浮/下沉各试一次；要做到 $O(\log n)$ 需要额外维护"元素 → 下标"的映射。

下一节衔接：上浮和下沉都讲完了，零件齐了。下一节把它们组装成一个完整的优先队列类，并和 .NET 内置的 PriorityQueue 对比 —— 包括它的 API 设计和那些容易踩的坑。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "11.2",
  "title": "上浮与下沉",
  "covered": [
    "两个方向相反的操作及各自的使用时机",
    "SiftUp 完整实现与逐步追踪（插入 1，2 次比较 2 次交换）",
    "SiftDown 完整实现与逐步追踪（删根后 1 次交换恢复）",
    "「插入必须放末尾」的实测反例（直接插根导致父子关系错乱）",
    "「删根用末尾顶替」的原因与图示",
    "上浮 vs 下沉的不对称（1 次 vs 最多 2 次比较）及其后果",
    "随机验证：200 插入 + 200 取出得到升序序列",
    "删除任意元素的两个方向与 O(log n) 优化方案"
  ],
  "unresolved": [
    "完整优先队列类的封装留到 11.3",
    "Top-K 与工程用法留到 11.4",
    "建堆 O(n) 的级数证明已在 8.3 节给出",
    "Dijkstra 用优先队列留到 13.3"
  ],
  "canonical_terms": {
    "上浮（Sift Up）": "把元素往上调整直到父节点不大于它，插入时用",
    "下沉（Sift Down）": "把元素往下调整直到它不大于孩子，删根/建堆时用",
    "堆序恢复（Heapify Up/Down）": "通过上浮或下沉重新满足堆序性质"
  },
  "symbols_units": {},
  "assumptions": [
    "读者已掌握 11.1 的堆定义与 8.3 的下沉/建堆",
    "读者理解 2.1 的递归与 3.4 的「指针只前进」概念"
  ],
  "word_count_actual": 2960,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch11/Sec112/",
    "上浮/下沉的逐步追踪、错误插入法的反例、200 次随机验证均为实测",
    "练习 11.2.1 的推演已手工验算（且验证了「插入1再取走1会回到原状」）",
    "术语写法与 glossary.md 一致"
  ],
  "next": "11.3 建堆与堆排序"
}

11.2　上浮与下沉