数组实现堆的关键是将完全二叉树层序遍历映射到数组，通过下标公式left=2i+1、right=2i+2、parent=(i−1)//2定位父子关系，这些公式源于层序编号的数学推导，而非硬背口诀；实际编码中必须检查边界条件以防越界。

数组实现堆结构的关键，在于把完全二叉树的层序遍历顺序“映射”到一维数组上，再通过下标公式快速定位父子关系。这不是硬背口诀，而是由编号方式自然导出的逻辑结果——理解这点，才能写对调整函数、避开越界错误、真正调试通堆操作。

为什么用数组？完全二叉树+层序编号是前提

堆的物理存储几乎总是数组，原因很实在：完全二叉树没有空洞，节点按层从左到右依次编号（根为第 0 个），填进数组就天然紧凑、无浪费。这个“层序编号”是所有索引公式的起点——不是约定，是推导基础。

• 根在索引 0，第 1 层两个节点占索引 1 和 2，第 2 层最多四个节点占索引 3–6……依此类推
• 若改用链式存储，就得额外维护指针，失去随机访问优势，也增加内存开销
• 数组下标从 0 开始是现代语言惯例，公式必须适配它；若从 1 开始，父子关系会更“对称”，但实际不采用

父子索引公式怎么来的？两个核心推导

公式 left = 2×i + 1、right = 2×i + 2、parent = (i − 1) // 2，都来自层序编号的数学关系，不是魔法数字。

• 左孩子 = 2×父 + 1：设父在第 d 层，本层起始索引是 2^d − 1，父在该层偏移为 k，则其下标 i = (2^d − 1) + k；它的左孩子在第 d+1 层，该层起始索引是 2^d+1 − 1，且排在该层第 2k 位 → 下标 = (2^d+1 − 1) + 2k = 2×i + 1
• 父节点 = ⌊(i − 1)/2⌋：若 i 是左孩子 → i = 2p + 1 → p = (i − 1)/2；若 i 是右孩子 → i = 2p + 2 → p = (i − 2)/2；整数除法下，两者统一为 (i − 1) // 2（C/Java/Python 中直接写 (i-1)/2 即可）

实际编码中必须检查的边界条件

公式只给出理论位置，真实数组有长度限制，每次计算孩子或父节点前，都要验证是否合法。

• 对父节点 i，左孩子存在 ⇔ 2×i + 1 < size；右孩子存在 ⇔ 2×i + 2 < size
• 对子节点 j，只要 j > 0，父节点 (j−1)//2 就一定有效；j == 0 是根，无父节点
• 向下调整时，常写 while(child < size)，但 child = parent×2 + 1 后，下一步要比较 child+1，必须先判断 child+1 < size，否则越界访问

两种调整操作如何依赖这些索引

建堆和维护堆的核心是向上调整（Insert）与向下调整（Pop/Heapify），它们都靠父子索引跳转完成比较与交换。

• 向上调整：新元素插在末尾（索引 size−1），然后不断和 parent = (child−1)//2 比较，若违反堆序（如大堆中孩子更大），就交换并更新 child = parent，直到触顶或满足序
• 向下调整：通常用于堆顶替换后（如 pop 后把末尾元素提到根）。从 parent = 0 开始，先算 left = 1、right = 2，选出较大（大堆）或较小（小堆）的孩子，再与 parent 比较；若需交换，更新 parent = child，重复直到孩子越界或满足序