algorithm - MAX-HEAPIFY : "the worst case occurs when the bottom level of the tree is exactly half full" 中的最坏情况

Question

在CLRS ，第三版，第 155 页，在 MAX-HEAPIFY 中给出，

"the worst case occurs when the bottom level of the tree is exactly half full"  

我猜原因是在这种情况下，Max-Heapify 必须通过左子树“向下 float ”。
但我无法得到的是“为什么半满”？
如果左子树只有一片叶子，Max-Heapify 也可以向下 float 。那么，为什么不将此视为最坏的情况呢？

Answer 1

阅读整个上下文:

The children's subtrees each have size at most 2n/3 - the worst case occurs when the last row of the tree is exactly half full

由于运行时间 T(n) 是通过树中元素的数量 (n) 来分析的，并且递归进入其中一个子树，我们需要找到子树中节点数的上限，相对于 n，这将产生 T(n) = T(max num. nodes in subtree) + O (1)

子树中节点数的最坏情况是最后一行的一侧尽可能满，而另一侧尽可能空。这称为半满。左子树的大小将以 2n/3 为界。

如果您提出的案例只有几个节点，那么这是无关紧要的，因为所有基本案例都可以被视为 O(1) 并被忽略。