MAX_HEAPIFY算法递归关系疑问：为何最坏场景需最大化左子树占比？

首先澄清一个认知误区：你提到的*「多加节点后下沉比较次数没变」是针对单个堆的下沉路径长度的直观感受，而CLRS中提到的「最坏情况发生在最后一层半满」，是用于推导时间复杂度递推关系的结论，核心是要找对任意规模n的堆，子问题规模占总规模的最大比值*，而非单次操作的绝对步骤数。

核心逻辑解释 #

堆是完全二叉树，最后一层节点全部靠左排列，因此根节点的左子树永远比右子树先填充节点：

• 当堆最后一层半满时，最后一层的所有节点都集中在左子树中，右子树是比左子树矮一层的满二叉树，此时左子树的规模达到当前堆高下的最大值，左子树大小L和总规模n的比值达到峰值约2/3。
• 当你继续往最后一层加节点时，左子树已经填满，新节点只能加到右子树中，此时左子树的大小L不再变化，总规模n持续上涨，L/n的比值会逐步下降。

具体示例 #

我们拿高度为3的堆举例：

1. 最后一层半满的场景：
   总节点数n=1（根节点）+7（左子树为高度2的满二叉树，共7个节点）+3（右子树为高度1的满二叉树，共3个节点）=11个节点。此时左子树占比为7/11≈0.64，接近2/3。如果根节点需要下沉到左子树最底层，子问题规模就是7，递推式为T(11) = T(7) + O(1)。
2. 最后一层多加1个节点的场景：
   新节点只能加到右子树的最后一层，总节点数n变成12，左子树大小还是7，占比变为7/12≈0.58，比半满场景的占比更低。此时根节点下沉到左子树最底层的步骤确实和之前一致，但子问题规模占总规模的比例下降，在递推时的上界不会超过半满的场景。

我们推导时间复杂度时需要取最紧的上界，所以只有L/n最大的半满场景，才是递推关系中的最坏情况。

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