为何堆化（heapify）从最后非叶节点向根遍历？为何不能从根开始？

堆化的核心逻辑很简单：让一个节点“下沉”到它应该在的位置——前提是这个节点的左右子树已经是合法的堆。这就是遍历顺序的关键。

为什么不能从根节点开始遍历？ #

假设我们从根节点开始堆化：

• 根节点下沉的时候，会和它的子节点交换位置，但这时候它的子树还没被堆化，本身就是乱的。
• 等后续处理子节点的时候，子节点的堆化操作会改变子树的结构，可能导致之前已经“处理好”的根节点位置不再符合堆的要求，但我们不会再回头重新处理根节点了。

举个实打实的例子，比如要把数组 [1,3,2,4,5] 堆化成大顶堆：

1. 从根节点（值为1）开始堆化：1比左子节点3小，交换后数组变成 [3,1,2,4,5]，此时根节点3看起来没问题。
2. 接着处理下一个非叶节点（索引1，值为1）：1比左子节点4小，交换后数组变成 [3,4,2,1,5]。
3. 遍历结束，但现在根节点3的左子节点是4，3 < 4，完全不符合大顶堆的要求！

这就是顺序错了的后果：子节点堆化后破坏了父节点原本的“正确”位置，而我们没有机会回溯修复。

为什么从最后一个非叶节点往上遍历就没问题？ #

从最后一个非叶节点开始，我们是从最底层的子树往上处理：

• 最底层的非叶节点，它的子节点都是叶子节点（叶子本身就是合法的堆），所以处理这个节点的时候，只需要把它和子节点中更大的那个交换，就能让这个子树变成合法堆。
• 往上处理父节点的时候，它的左右子树已经被我们处理过了，都是合法的堆。这时候只需要把当前节点下沉到左右子树的正确位置，整个子树就会变成合法堆，而且不会破坏已经处理好的下层结构。

还是用刚才的例子 [1,3,2,4,5]：

1. 先处理最后一个非叶节点（索引1，值为3）：它的子节点是4和5，3比5小，交换后数组变成 [1,5,2,4,3]，此时索引1的子树（5、4、3）是合法大顶堆。
2. 再处理根节点（值为1）：它的子节点是5和2，1比5小，交换后数组变成 [5,1,2,4,3]；接着继续下沉1，它的子节点是4和3，1比4小，交换后变成 [5,4,2,1,3]，此时整个树就是合法的大顶堆了。

遍历顺序到底重要在哪？ #

虽然每个非叶节点都会被访问，但顺序决定了处理当前节点时，依赖的子树状态是否合法。从下往上遍历，每一步都站在“已经处理好的子树”基础上，堆化操作一次到位；从上往下遍历，子树的后续调整会破坏之前的成果，最终可能得到错误的堆结构。

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