在CLRS的第三版第155页中，给出了MAX-HEAPIFY算法的实现：
"the worst case occurs when the bottom level of the tree is exactly half full"
我猜原因是在这种情况下，Max-Heapify必须通过左子树“向下漂浮”。
但我不明白的是“为什么是半满的”？
如果左子树只有一个叶子节点，Max-Heapify也可以向下漂浮。那么为什么不把这个情况考虑为最坏情况呢？
2个回答
13
阅读整个上下文：
每个子树的大小最多为2n/3 - 最坏情况是树的最后一行正好半满
由于运行时间 T(n) 是通过树中元素的数量 (n) 进行分析的，并且递归步骤进入其中一个子树，因此我们需要找到相对于 n 的子树节点数的上限，并且这将产生 T(n) = T(子树中的最大节点数) + O(1)
子树中节点数的最坏情况是当最后一行在一侧尽可能充满，在另一侧尽可能空置。这被称为半满。左子树大小将受到 2n/3 的限制。
如果您提出的情况只有几个节点，则无关紧要，因为所有基本情况都可以视为 O(1) 并忽略。
- davin
5
8
已经有一个被接受的答案，但这个答案是给那些仍然有点困惑（像我一样）或者还没有理解的人的。所以这里有一个稍微更长、更详细的解释。虽然听起来可能有些冗余，但我们必须非常清楚确切的定义，因为通过我们对细节的关注... 当你这样做时，证明事情变得更容易了。从CLRS（第6.1节）中，二叉堆数据结构是一个可以被视为几乎完全二叉树的数组对象。从Wikipedia中，一个完全二叉树中，每个层级（除了可能是最后一层）都是完全填充的，并且最后一层的所有节点都尽可能地在左侧。同样，从Wikipedia中，平衡二叉树是一种二叉树结构，在这种结构中，每个节点的左子树和右子树的高度差不超过1。
现在我们有了武器，让我们开始吧。
因此，与根相比，左右子树的高度最多可以相差1。
让我们考虑一棵树T，左子树的高度为h+1，右子树的高度为h。
在MAX_HEAPIFY中可能出现的最坏情况是什么？最坏情况发生在我们试图维护堆属性时进行最大数量的比较和交换。
当MAX_HEAPIFY算法运行并且如果它递归地通过最长路径，则我们可以考虑可能的最坏情况，因为它将在最长路径上做出最大数量的比较和交换。
嗯，似乎所有最长的路径都在左子树中（因为它的高度为h+1）。但是有人也可能会问：为什么不是右子树？请记住上面的定义，最后一层中的所有节点必须尽可能向左。
现在因为我们必须覆盖可能导致最坏情况的每种可能性，所以我们需要更多数量的更长路径（如果存在），因此，我们应该使左子树充满（但为什么？这样我们就可以得到更多选择的路径，并选择所有路径中给出最坏情况时间的路径）。
由于左子树的高度为h+1，它将具有2^(h+1)个叶节点，因此从根节点开始有2^(h+1)条路径。这是高度为h+1的树T中可能的路径的最大数量。
注意：如果您仍在阅读，请保留它，也许只是为了更加清晰明了。
以下是最坏情况下树结构的image。
在上面的图像中，如您所见，考虑左侧（黄色）子树和右侧（粉色）子树各具有x个节点。粉色部分是完整的右子树，黄色部分是除最后一层之外的左子树。
请注意，左子树（黄色）和右子树（粉色）的高度均为h。
从一开始，我们就将左子树作为整体考虑为高度h+1（即包括黄色部分和最后一层）。
现在，我想问一下，在黄色部分以下的最后一层中，我们需要添加多少个节点才能使左子树完全满？
好的，黄色部分的最底层有⌈x/2⌉个节点（即具有n个节点的树/子树中总叶数=⌈n/2⌉；有关证明，请访问this链接），现在如果我们每个节点或叶子都添加2个子节点=>总共添加x（≈x）个节点（如何？⌈x/2⌉叶* 2 ≈ x节点）。
通过这种添加，我们使左子树的高度为h+1（即高度为h的黄色部分和添加的最后一层），因此满足最坏情况的条件。
由于左子树是满的，整个树是半满的。现在有人可能会问：如果我们添加更多节点，或者具体地说，如果我们在右子树中添加节点会怎样？好吧，我们不会这样做。这是因为现在如果我们恰好添加更多节点，则节点将被添加到右子树中（因为左子树已经满了），这反过来又会倾向于使树更加平衡。现在随着树开始变得更加平衡，我们正在朝着最佳情况而不是最坏情况迈进。最后一个问题：我们总共有多少节点？树中的总节点数n = x（黄色部分）+ x（粉色部分）+ x（添加在黄色部分下面的最后一层）= 3x。你能注意到什么吗？作为副产品，左子树总共包含最多2x个节点，即2n / 3个节点（因为x = n / 3）。
现在我们有了武器，让我们开始吧。
因此，与根相比，左右子树的高度最多可以相差1。
让我们考虑一棵树T，左子树的高度为h+1，右子树的高度为h。
在MAX_HEAPIFY中可能出现的最坏情况是什么？最坏情况发生在我们试图维护堆属性时进行最大数量的比较和交换。
当MAX_HEAPIFY算法运行并且如果它递归地通过最长路径，则我们可以考虑可能的最坏情况，因为它将在最长路径上做出最大数量的比较和交换。
嗯，似乎所有最长的路径都在左子树中（因为它的高度为h+1）。但是有人也可能会问：为什么不是右子树？请记住上面的定义，最后一层中的所有节点必须尽可能向左。
现在因为我们必须覆盖可能导致最坏情况的每种可能性，所以我们需要更多数量的更长路径（如果存在），因此，我们应该使左子树充满（但为什么？这样我们就可以得到更多选择的路径，并选择所有路径中给出最坏情况时间的路径）。
由于左子树的高度为h+1，它将具有2^(h+1)个叶节点，因此从根节点开始有2^(h+1)条路径。这是高度为h+1的树T中可能的路径的最大数量。
注意：如果您仍在阅读，请保留它，也许只是为了更加清晰明了。
以下是最坏情况下树结构的image。
在上面的图像中，如您所见，考虑左侧（黄色）子树和右侧（粉色）子树各具有x个节点。粉色部分是完整的右子树，黄色部分是除最后一层之外的左子树。
请注意，左子树（黄色）和右子树（粉色）的高度均为h。
从一开始，我们就将左子树作为整体考虑为高度h+1（即包括黄色部分和最后一层）。
现在，我想问一下，在黄色部分以下的最后一层中，我们需要添加多少个节点才能使左子树完全满？
好的，黄色部分的最底层有⌈x/2⌉个节点（即具有n个节点的树/子树中总叶数=⌈n/2⌉；有关证明，请访问this链接），现在如果我们每个节点或叶子都添加2个子节点=>总共添加x（≈x）个节点（如何？⌈x/2⌉叶* 2 ≈ x节点）。
通过这种添加，我们使左子树的高度为h+1（即高度为h的黄色部分和添加的最后一层），因此满足最坏情况的条件。
由于左子树是满的，整个树是半满的。现在有人可能会问：如果我们添加更多节点，或者具体地说，如果我们在右子树中添加节点会怎样？好吧，我们不会这样做。这是因为现在如果我们恰好添加更多节点，则节点将被添加到右子树中（因为左子树已经满了），这反过来又会倾向于使树更加平衡。现在随着树开始变得更加平衡，我们正在朝着最佳情况而不是最坏情况迈进。最后一个问题：我们总共有多少节点？树中的总节点数n = x（黄色部分）+ x（粉色部分）+ x（添加在黄色部分下面的最后一层）= 3x。你能注意到什么吗？作为副产品，左子树总共包含最多2x个节点，即2n / 3个节点（因为x = n / 3）。
- Aarush Aggarwal
1
最佳答案。解决了所有疑惑。 - 0xPrateek
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
T(n) = T(s(n)) + O(1)感兴趣，所以我们需要找到s(n) = subtree size as a function of n的最坏情况。说我们正在“最大化子树的大小”是不正确的（我在与此问题相关的其他答案中看到过这种说法）- 我们真正最大化的是左右子树大小之比L/R。 - rmorshea