在最大堆化算法中，验证左右元素是否小于堆大小的目的是什么？

Question

这是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 largest <- i
[...]

验证左堆的索引是否小于输入中给定的堆 A 的大小的目的是什么？

Answer 1

这里的l(左(和r(右(是左右子项的索引值，而不是值本身，因此为了确保索引(l&r(不超过堆(存储为数组的堆(的大小，我们根据堆大小检查它。