堆为什么用数组存储？父子节点的下标关系是什么？

简化版

因为堆是完全二叉树（节点从上到下、从左到右连续排列，中间没有空洞），所以可以按层序「压平」成一个数组，不需要存左右指针，靠下标计算就能找到父子。以 0 开始编号：节点 i 的左孩子 2i+1、右孩子 2i+2、父节点 (i-1)/2。省内存、连续存储缓存友好。

详细版

完全二叉树按层序（从上到下、每层从左到右）给节点编号，正好和数组下标一一对应，中间不会有空位：

        9(0)
       /    \
     7(1)    8(2)
    /   \    /
  3(3) 5(4) 6(5)

数组: [9, 7, 8, 3, 5, 6]
       0  1  2  3  4  5

下标关系（0-indexed，最常用）：

关系	公式
节点 i 的左孩子	`2i + 1`
节点 i 的右孩子	`2i + 2`
节点 i 的父节点	`(i - 1) / 2`（整除）
最后一个非叶子节点	`n/2 - 1`（n 为元素个数）

若用 1-indexed（下标从 1 开始）：左孩子 2i、右孩子 2i+1、父 i/2，公式更简洁，有些实现会故意空出下标 0。

完整版教学

一、为什么完全二叉树能用数组存

普通二叉树形状不规则，有的节点缺左孩子、有的缺右孩子，只能用「节点 + 左右指针」的链式结构存储。而完全二叉树非常规整：除了最后一层，每层都填满；最后一层也是从左往右连续排列，中间绝不留空。这个「无空洞」的特性让它可以按层序直接铺进数组，第 0 个位置放根，接着放第二层……一个萝卜一个坑，不浪费空间。

二、下标公式是怎么来的

以 0-indexed 为例，按层序编号：根是 0，它的两个孩子是 1、2；下一层是 3、4、5、6……观察规律，节点 i 的：

左孩子 = 2i + 1，右孩子 = 2i + 2。
反过来，孩子 c 的父节点 = (c-1)/2（整除）。

验证：节点 1 的左孩子 2×1+1=3、右孩子 2×1+2=4，父节点 (1-1)/2=0（根）。✓ 这套公式让我们不用任何指针，纯靠算术就能在数组里上下移动，这是堆所有操作（上浮、下沉）的基础。

三、数组存储的三大好处

省内存：不用存左右孩子指针，每个节点少两个指针的开销。
缓存友好：数组是连续内存，堆的上浮/下沉沿着父子链跳转，局部性好，比链式结构快。
实现简单：上浮下沉就是数组下标的计算和交换，代码短、不易错。

这就是为什么所有主流堆（Java PriorityQueue、C++ priority_queue）底层都是数组，而不是真的用树节点+指针。

四、最后一个非叶子节点：n/2 - 1

建堆时要从「最后一个非叶子节点」开始往前遍历。它的下标是 n/2 - 1（n 为元素总数）。原因：最后一个元素的下标是 n-1，它的父节点就是 (n-1-1)/2 = n/2 - 1。而这个父节点正是「最靠后的、还有孩子的节点」——它之后的节点全是叶子（没有孩子，不需要下沉）。这个下标在建堆和堆排序里频繁用到。

五、易错点

0 还是 1 开始：两套公式不同，写代码前先定好。0-indexed 是主流（Java 用它），但 1-indexed 公式更漂亮。别混用。
父节点用整除：(i-1)/2 对左右孩子都成立（如 i=3、4 的父都是 1）。
越界检查：算出孩子下标后要判断 < n 才是有效节点，否则越界。

六、常见误区与追问

考点	正确口径
父节点	`parent = (i - 1) / 2`
左孩子	`left = 2 * i + 1`
右孩子	`right = 2 * i + 2`

0-based heap:
i = 3
left = 7
right = 8
parent = 1

堆能用数组存，是因为它必须是完全二叉树，层序编号不会留下结构空洞。

误区：任何二叉树都适合直接用数组紧凑存储。 普通二叉树可能有大量空洞；堆是完全二叉树，层序数组才紧凑。
误区：0 下标和 1 下标公式可以混用。 0 下标是 2i+1/2i+2，1 下标是 2i/2i+1，混用会访问错位置。
误区：堆数组一定是整体有序的。 数组只满足父子堆序，兄弟之间和跨层节点不保证全局排序。
追问：最后一个非叶子节点如何求？ 0 下标为 n/2 - 1，从这里往后都是叶子，无需下沉。
追问：数组存储相比指针树有什么优势？ 节省指针空间、缓存局部性好、父子定位只需下标计算。
追问：删除堆顶为什么用最后一个元素补？ 这样能保持完全二叉树形状，再通过下沉恢复堆序。

七、加强记忆

堆是完全二叉树（无空洞），能按层序压进数组、免指针。0-indexed 下标关系：左孩子 2i+1、右孩子 2i+2、父 (i-1)/2，最后一个非叶子节点 n/2-1。数组存储省内存、缓存友好、实现简单，是所有主流堆的底层。写代码前先定 0 还是 1 起始（公式不同），算出孩子下标要判越界。

简化版

详细版