小根二叉堆（Min Heap，又称最小堆）是数据结构和算法竞赛（CSP-J/S、NOIP、海中自招）中出场率最高、性价比最强的底层结构。C++ STL 里的 priority_queue 底层就是基于它实现的。

一、什么是小根堆？（两大硬性特征）

一个小根二叉堆必须同时满足以下两个条件：

1. 结构特征：它必须是一棵“完全二叉树”
   • 除了最底层，所有层都是满的；
   • 最底层的节点全部严格从左到右紧密排列，中间绝不能有空隙。
2. 堆序特征：父节点永远 $\le$ 子节点
   • 对于树中任意一个父节点：$val(父) \le val(左孩子)$ 且 $val(父) \le val(右孩子)$。
   • 必然推论：堆顶（根节点）永远是整棵树的全局最小值！

初赛经典辨析坑点：

• 小根堆不是二叉搜索树（BST）！
• 堆只约束“父子关系”，不约束左右兄弟之间的大小（左孩子比右孩子大或小都可以）。

二、堆的数组顺序存储（必考下标公式）

由于完全二叉树的紧密性，我们在实现堆时根本不需要写指针，直接用一个一维数组就能存下。

通常从下标 1 开始存储（下标 0 闲置）：

• 根节点在：1
• 任意节点 $i$ 的：
  • 父节点：$\lfloor i / 2 \rfloor$（如节点 6 的父亲是 $6/2=3$）
  • 左孩子：$2i$（如节点 3 的左孩子是 $3 \times 2 = 6$）
  • 右孩子：$2i + 1$（如节点 3 的右孩子是 $3 \times 2 + 1 = 7$）

       [3] (下标 1)
      /   \
    [7]   [5] (下标 2, 3)
   /  \   /
 [12] [9][8] (下标 4, 5, 6)

对应数组：[-, 3, 7, 5, 12, 9, 8]

三、两大核心操作（手推过程）

1. 插入新元素（Push）——“上浮（Sift Up）”

• 步骤：
  1. 把新元素直接塞到数组末尾（即树的最底层最右侧空位）；
  2. 拿它和它的父节点比较：若比父亲小，就和父亲交换位置；
  3. 重复向上比较并交换，直到它不再小于父亲，或者已经浮到了堆顶（根节点）。
• 时间复杂度：完全二叉树的高度为 $\log_2 n$，最坏只需交换 $\log n$ 次，耗时 $O(\log n)$。

2. 弹出堆顶最小值（Pop）——“下沉（Sift Down）”

• 为什么不能直接删根节点？ 会导致整棵树裂成两棵独立的子树，无法用数组连续维护。
• 标准操作步骤（考试重点考这个手推）：
  1. 取出堆顶 heap[1]（最小值）；
  2. 将数组最后一个元素挪到堆顶 heap[1]，同时堆大小减 1；
  3. 下沉调整：
     • 找到当前节点的左右孩子中较小的那一个；
     • 如果当前节点比这个较小的孩子还要大，就和这个较小的孩子交换；
     • 顺着该分支继续重复比较，直到它比左右两个孩子都小，或者已经成为叶子节点。
• 时间复杂度：最坏一路下沉到叶子，耗时 $O(\log n)$。

四、手算实战演示（就是你模拟卷里的第 6 题）

假设当前小根堆数组为：[-, 3, 7, 5, 12, 9, 8, 10]（共 7 个元素）：

        (1) [3]
        /      \
    (2)[7]     (3)[5]
    /    \     /    \
  (4)[12](5)[9](6)[8] (7)[10]

现执行一次 Pop 操作：

1. 弹出最小值 3；
2. 将末尾的 10 放到堆顶（下标 1），堆大小变为 6；
3. 第一轮下沉（当前在下标 1，值为 10）：
   • 左孩子下标 2（值 7），右孩子下标 3（值 5）；
   • 挑较小孩子：右孩子 5；
   • 因为 $10 > 5$，交换 10 和 5。此时 5 成为新堆顶，10 来到下标 3。
4. 第二轮下沉（当前在下标 3，值为 10）：
   • 左孩子下标 $3 \times 2 = 6$（值 8）；右孩子下标 7（已越界无右孩子）；
   • 比较 10 和左孩子 8：因为 $10 > 8$，交换 10 和 8。8 来到下标 3，10 最终落入下标 6。
5. 下标 6 已经没有孩子了，下沉完毕！ 最终数组变为：[-, 5, 7, 8, 12, 9, 10]。

五、考场核心结论与记忆清单