我想要一个直观的解释，说明为什么我们不从0 遍历到 (n / 2) - 1

我们仍然会访问每个子树并对其进行堆化，所以顺序为什么会重要？并不是说树的结构本身会改变。

解决方案

引用《算法导论》（Cormen、Leiserson、Rivest，1999）§7.2，“维持堆性质”：

当调用HEAPIFY时，假设以LEFT(i) 和RIGHT(i) 为根的二叉树是堆，但 A[i] 可能小于它的子节点……

因此，当调用 §7.3的 BUILD-HEAP时，需要从树的底部开始——最后一个非叶子索引——向上工作。如果你从根开始向下进行，那么就破坏了节点 i 的两个子节点已经是堆这一变体。

相应的细节是，HEAPIFY是将顶部节点向下推，但不一定把较低的节点往上拉起来。因此如果你以这样的树开始：

    0
   / \
  2   1
 / \
3   4

并对这两个非叶节点调用HEAPIFY，但把根节点放在先，首先值为0 的节点被向底部推到

    2
   / \
  4   1
 / \
3   0

然后你访问现在值为4 的子树，看起来正确，因此你就完成了；但最大的值并不在根上，因此你还没有建立一个堆。自下而上地执行就会得到

    0           *0*            4
   / \          / \           / \
 *2*  1  -->   4   1  -->    3   1
 / \          / \           / \
3   4        3   2         0   2

此时以3 为根的子树，以及以4 为根的整棵树，都是堆。

一个纯粹直观的理解是，HEAPIFY只是在查看当前节点，并可能让它沿着树向下走一个线性的路径被推下去；因此每次对HEAPIFY的调用都需要O(log n) 的时间，BUILD-HEAP调用HEAPIFY O(n) 次，构建一个堆需要O(n log n) 的时间。（§7.4还进一步讨论了为什么堆排序也需要O(n log n) 的时间。）但是，索引0 必然包含整个堆中的最大元素，找到它需要O(n) 的时间。