堆排序“Heapify”迭代过程
我正在检查 max-heapify 算法的迭代方法，以下是 CLRS 解决方案中给出的内容。
while i < A.heap-size do
l =LEFT(i)
r =LEFT(i)
largest = i
if l ≤ A.heap-size and A[l] > A[i] then
largest = l
end if
if r ≤ A.heap-size and A[r] > A[i] then
largest = r
end if
if largest not equal i then
exchange A[i] and A[largest]
i = largest
else return A
end if
end while
return A
我的问题是为什么循环条件给出为 i i i i i i i i i i i i < A.堆大小？由于左右应该在堆大小之内，这意味着父级必须是？i <= A.heap-size/2，为什么我们不能检查这样的条件<代码>i<=A.heap-size/2
I was checking the iterative approach for the max-heapify algorithm and the following is what is given in CLRS solutions.
while i < A.heap-size do
l =LEFT(i)
r =LEFT(i)
largest = i
if l ≤ A.heap-size and A[l] > A[i] then
largest = l
end if
if r ≤ A.heap-size and A[r] > A[i] then
largest = r
end if
if largest not equal i then
exchange A[i] and A[largest]
i = largest
else return A
end if
end while
return A
My question is why the loop condition is given as i < A.heap-size? Since the left and right should be within the heap size, which would mean that the parent must be i <= A.heap-size/2, why can't we check the condition as such i<=A.heap-size/2?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
是的，你是对的，检查到堆大小/2 就足够了。之后我们甚至没有这些节点的子节点。
Yeah you are correct , it is just sufficient to check till heap-size/2. After that we don't even have children for those nodes.