在CLRS，第三版，第 155 页，给出了在 MAX-HEAPIFY 中，
"the worst case occurs when the bottom level of the tree is exactly half full"
我猜原因是在这种情况下，Max-Heapify 必须通过左子树“向下浮动”。
但我无法得到的是“为什么半满”？
如果左子树只有一个叶子，Max-Heapify 也可以向下浮动。那么为什么不认为这是最坏的情况呢？
问问题
8944 次
2 回答
10
阅读整个上下文：
子树的每个子树的大小最多为 2n/3 - 最坏的情况发生在树的最后一行正好是半满时
由于运行时间是通过树中T(n)元素的数量来分析的（那nnT(n) = T(max num. nodes in subtree) + O(1)
子树中节点数的最坏情况是最后一行在一侧尽可能满，而在另一侧尽可能空。这称为半满。并且左子树的大小将以 为界2n/3。
如果您提出的案例只有几个节点，那么这无关紧要，因为可以考虑O(1)并忽略所有基本案例。
于 2011-07-28T13:29:42.450 回答
3
我知道已经有一个公认的答案，但是对于那些有同样问题并且仍然有点困惑（就像我一样）的人，或者不清楚的人——这里有一点更长更详细的解释。
虽然这听起来可能很无聊或多余，但我们必须非常清楚确切的定义，因为通过关注细节——当你这样做时，证明事情会变得容易得多。
从 CLRS 第 6.1 节，（二进制）堆数据结构是一个数组对象，我们可以将其视为几乎完整的二叉树
来自维基百科，在完整的二叉树中，除了可能的最后一层之外，每一层都被完全填满，并且最后一层中的所有节点都尽可能远离。
此外，来自维基百科，平衡二叉树是一种二叉树结构，其中每个节点的左右子树的高度差不超过 1。
因此，与根相比，左右子树的高度最大可以相差 1。
现在，考虑一棵树 T，让左子树的高度 = h+1，右子树的高度 = h
MAX_HEAPIFY 中最坏的情况是什么？最坏的情况是当我们在试图维护堆属性的同时进行更多的比较和交换。
如果 MAX_HEAPIFY 算法运行并且递归地通过最长路径，那么我们可以考虑可能的最坏情况。
好吧，所有最长的路径都在左子树中（因为它的高度是 h+1）。为什么不是正确的子树？记住定义，最后一层的所有节点都必须尽可能的靠左。
因此，为了获得更多数量的最长路径，我们应该使左子树 FULL（为什么？这样我们就可以有更多路径可供选择并选择给出最坏情况时间的路径）。由于左子树的高度为 h+1，它将有 2^(h+1) 个叶节点，因此从根开始有 2^(h+1) 个最长路径。这是树 T（高度为 h+1）中最长路径的最大可能数。
这是最坏情况下的树结构图像。
从上图中，考虑黄色（左）和粉红色（右）子树各有 x 个节点。粉色部分是完整的右子树，黄色部分是不包括最后一层的左子树。
请注意，黄色（左）和粉红色（右）子树的高度均为 h。
现在，从一开始，我们就认为左子树作为一个整体的高度为 h+1（包括黄色部分和最后一层），如果我可以问，我们需要添加多少个节点最后一层，即黄色部分下方，使左子树完全充满？
好吧，黄色部分的最底层有 ⌈x/2⌉ 个节点（具有 n 个节点的树/子树中的叶子总数 = ⌈n/2⌉；为了证明，请访问此链接），现在如果我们向这些节点/叶子中的每一个添加 2 个子节点，=> 总共添加了 x (≈x) 个节点（如何？⌈x/2⌉ 叶子 * 2 ≈ x 个节点）。
通过这个添加，我们使高度为 h+1 的左子树（高度为 h 的黄色部分 + 最后一层添加）和 FULL，因此满足最坏情况的标准。
由于左子树是FULL，所以整个树是半满的。
现在，最重要的问题——我们为什么不在右子树中添加更多节点或添加节点？好吧，那是因为现在如果我们倾向于添加更多节点，则必须将节点添加到右子树中（因为左子树已满），这反过来又会使树更加平衡. 现在随着树开始变得更加平衡，我们倾向于朝着最好的情况而不是最坏的情况前进。
另外，我们总共有多少个节点？
树的总节点数 n = x（来自黄色部分）+ x（来自粉红色部分）+ x（在黄色部分下方的最后一层相加）= 3x
请注意，作为副产品，左子树总共包含最多 2x 个节点，即 2n/3 个节点（x = n/3）。
于 2021-05-16T10:35:56.627 回答