在CLRS，第三版，第155页中，假定在MAX- HEAPIFY中，
"the worst case occurs when the bottom level of the tree is exactly half full"
我猜想原因是在这种情况下，Max-Heapify必须通过左侧子树“向下浮动”。 但是我无法得到的是“为什么半满”？ 如果左侧子树只有一个叶子，则Max-Heapify也可以向下浮动。那么，为什么不将其视为最坏的情况呢？
阅读整个上下文：
子树的每个子树的大小最大为2n / 3-最坏的情况是树的最后一行恰好占满一半时
由于运行时间T(n)是根据树（n）中的元素数量进行分析的，并且递归过程进入了子树之一，因此我们需要找到子树中相对于的节点数的上限n，这将产生那T(n) = T(max num. nodes in subtree) + O(1)
T(n)
n
T(n) = T(max num. nodes in subtree) + O(1)
子树中节点数的最坏情况是最后一行的一侧尽可能地满，而另一侧则尽可能地空。这称为半满。并且左子树的大小将由限制2n/3。
2n/3
如果您提出的案例中只有几个节点，那么这是无关紧要的，因为可以考虑O(1)并忽略所有基本案例。
O(1)
