algorithm - 在 Max-Heapify 算法中，验证左右元素小于堆大小的目的是什么？

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(left) 和r(right) 是左右孩子的索引值，而不是值本身，所以要确保索引 (l & r) 不超过堆的大小（堆存储为数组）我们根据堆大小检查它。