在Max-Heapify算法中，验证left和right元素是否小于堆大小的目的是什么？

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)不超过堆(堆存储为数组)的大小，我们对照堆大小进行检查。