构建最大堆为何从⌊length[A]/2⌋倒序到1而非正序遍历？

核心原因：MAX-HEAPIFY的调用前提限制 #

MAX-HEAPIFY 函数生效有一个必须满足的前置条件：待处理节点 i 的左子树、右子树本身已经是合法的最大堆，它只能在这个前提下将 i 位置的元素下沉，最终让以 i 为根的整棵子树符合最大堆性质。 #

倒序建堆（从⌊length[A]/2⌋递减到1）的合理性 #

• 所有索引大于⌊length[A]/2⌋的节点都是叶子节点，单节点天然是合法最大堆，不需要额外处理。
• 倒序遍历时，每次处理节点i，它的左子节点2i、右子节点2i+1的索引都大于i，要么是已经处理完成的非叶子节点，要么是天然合法的叶子节点，完全满足MAX-HEAPIFY的调用前提。每处理完一个i，以i为根的子树就成为合法最大堆，最终遍历到根节点1处理完成后，整个数组就是合法最大堆。

正序建堆的问题 #

正序从1递增到⌊length[A]/2⌋的遍历方式，处理节点i时，它的左右子树都还没有经过处理，不满足MAX-HEAPIFY的前置条件，绝大多数场景下最终都无法得到合法最大堆。
你之前的测试用例只是碰巧得到了正确结果，我们可以用一个简单的反例验证问题：
测试数组：A = <4, 1, 3, 2, 16>，数组长度为5，⌊length[A]/2⌋=2

1. 正序建堆流程：
   先处理i=1：此时左右子树都未经过处理，MAX-HEAPIFY对比A[1]=4和子节点A[2]=1、A[3]=3，最大值为4，无需交换，处理后数组不变。
   再处理i=2：对比A[2]=1和子节点A[4]=16，交换得到数组<4, 16, 3, 2, 1>。
   最终得到的数组根节点为4，子节点为16，明显违反最大堆父节点大于子节点的性质。
2. 倒序建堆流程：
   先处理i=2：对比A[2]=1和子节点A[4]=16，交换得到数组<4, 16, 3, 2, 1>，此时以2为根的子树已经是合法最大堆。
   再处理i=1：左右子树均为合法最大堆，MAX-HEAPIFY对比A[1]=4和子节点A[2]=16、A[3]=3，交换4和16，得到最终合法最大堆<16, 4, 3, 2, 1>。

内容的提问来源于stack exchange，提问作者Avv