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