最大堆化算法中，验证左右子节点索引≤堆大小的作用是什么？

先把完整的MAX-HEAPIFY伪代码放出来方便参考：

MAX-HEAPIFY(A, i)
1. l ← Left(i)
2. r ← Right(i)
3. if l ≤ heap-size[A] and A[l] > A[i]
4.     largest ← l
5. else
6.     largest ← i
7. if r ≤ heap-size[A] and A[r] > A[largest]
8.     largest ← r
9. if largest ≠ i
10.    exchange A[i] ↔ A[largest]
11.    MAX-HEAPIFY(A, largest)

这是个很好的问题，这个边界检查是MAX-HEAPIFY能正确运行的核心保障之一，主要作用有这几点：

• 彻底避免数组越界问题：堆是用数组底层实现的，但heap-size[A]才是当前堆里实际有效元素的数量——数组本身的长度可能比堆的实际大小要大（比如初始化堆后可能有未被纳入堆的闲置元素）。如果跳过这个检查，当节点i是堆的叶子节点时，它的左/右子节点索引会超出堆的有效范围，访问A[l]或A[r]就会读取到堆外的无效数据，甚至直接触发数组越界的错误。

• 只处理堆内的有效节点：堆的结构规则只对heap-size[A]范围内的元素生效。叶子节点本身没有子节点，当l或r超过堆大小时，就意味着对应的子节点根本不存在，自然没必要参与“找最大值”的比较逻辑——不存在的节点不可能比当前节点更大。

• 确保递归能正常终止：当我们递归调用MAX-HEAPIFY(A, largest)时，如果largest指向的是叶子节点，它的左右子节点索引会直接超过堆大小，这时候不会进入后续的比较和递归操作，递归链就会自然终止，避免出现无限递归的情况。

举个直观的例子：假设堆的有效大小是5（元素存在A[1]到A[5]），当处理节点i=3时，Left(i)=6，这时候6>5，说明这个节点没有左子节点，直接跳过比较，把largest设为i本身，完全不会去碰A[6]这个无效位置。

内容的提问来源于stack exchange，提问作者Alexia