MAX-HEAPIFY的最坏情况:"最坏的情况发生在树的底层正好是半满的时候"

Question

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

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

我想原因是在这种情况下,Max-Heapify必须通过左子树"向下浮动".
但我无法得到的是"为什么半满"？
如果左子树只有一个叶子,Max-Heapify也可以向下浮动.那么为什么不把这视为最坏的情况呢？

Answer 1

阅读整个上下文:

孩子们的子树每个都有2n/3的大小 - 最坏的情况发生在树的最后一行正是半满的时候

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

子树中节点数最坏的情况是最后一行在一侧尽可能满,而在另一侧尽可能为空.这被称为半满.左边的子树大小将受到限制2n/3.

如果你提议只有几个节点的情况,那就无关紧要了,因为所有基本情况都可以被考虑O(1)和忽略.

Answer 2

已经有一个公认的答案，但这个答案是为那些仍然有点困惑的人（就像我一样），或者仍然没有点击的东西。这里有一个更长、更详细的解释。

\n

虽然这听起来可能多余，但我们必须非常清楚确切的定义，因为通过我们对细节的关注……当你这样做时，证明事情可能会变得容易得多。

\n

从 CLRS（第 6.1 节）来看，二叉堆数据结构是一个数组对象，可以将其视为几乎完整的二叉树

\n

从维基百科来看，在完全二叉树中，每一层（可能除了最后一层）都被完全填满，并且最后一层的所有节点都尽可能靠左。

\n

同样，根据维基百科，平衡二叉树是一种二叉树结构，其中每个节点的左右子树的高度相差不超过1。

\n

现在我们已经武装好了，让我们开始吧。

\n

因此，与根相比，左右子树的高度最多可以相差1 。

\n

让我们考虑一棵树 T ，令左子树的高度 = h+1 ，右子树的高度 = h

\n

MAX_HEAPIFY 中最坏的情况是什么？当我们在尝试维护堆属性的同时最终进行最大数量的比较和交换时，就会发生最坏的情况。

\n

当 MAX_HEAPIFY 算法运行时，如果它递归地遍历最长路径，那么我们可以考虑可能的最坏情况，因为它将最终在最长路径中进行最大数量的比较和交换。

\n

好吧，似乎所有最长的路径都恰好位于左子树中（因为它的高度为 h+1）。但有人可能会问：为什么不是正确的子树呢？记住上面的定义，最后一层的所有节点都必须尽可能靠左。

\n

现在，因为我们必须涵盖可能导致最坏情况的所有可能性，所以我们需要获得更多数量的较长路径（如果存在），因此，我们应该使左侧（但是为什么呢？这样我们就可以有更多的路径可供选择，并选择给出最坏情况时间的路径）。

\n

由于左子树的高度为 h+1，因此它将有 2^(h+1) 个数。叶节点，因此，从根开始的路径数为 2^(h+1)。这是高度为 h+1 的树 T 中可能路径的最大数量。

\n

注意：如果您仍在阅读，请继续阅读，也许只是为了清晰起见。

\n

这是最坏情况下的树结构图像。

\n

在上图中，如您所见，左子树（黄色）和右子树（粉红色）各有 x 个节点。粉红色部分是完整的右子树，黄色部分是不包括最后一层的左子树。

\n

请注意，左侧（黄色）和右侧（粉色）子树的高度均为 h。

\n

现在，从一开始，我们就认为左子树整体的高度为h+1（即包括黄色部分和最后一层）。

\n

现在，如果我可以问，我们必须在最后一层（即黄色部分下方）添加多少个节点才能使左子树完全充满？

\n

好吧，黄色部分的最底层有 \xe2\x8c\x88x/2\xe2\x8c\x89 个节点（即具有 n 个节点的树/子树中的叶子总数 = \xe2\x8c\x88n/2 \xe2\x8c\x89；为了证明，请访问此链接），现在如果我们向每个节点或叶子添加 2 个子节点 => 已添加总共 x (\xe2\x89\x88x) 个节点（如何？\xe2\ x8c\x88x/2\xe2\x8c\x89 叶子 * 2 \xe2\x89\x88 x 节点）。

\n

通过这一添加，我们使高度为 h+1 的左子树（即高度为 h 的黄色部分和添加的最后一层）为 FULL，从而满足最坏情况的标准。

\n

由于左子树是FULL，因此整个树是HALF FULL。

\n

现在有人可能会问：如果我们添加更多节点怎么办，或者具体来说，如果我们在右子树中添加节点怎么办？嗯，我们不这样做。这是因为现在如果我们碰巧添加更多节点，这些节点将被添加到右子树中（因为左子树已满），这反过来又会更加平衡树。现在，随着树开始变得更加平衡，我们倾向于朝着最好的情况而不是最坏的情况发展。

\n

最后一个问题：我们总共有多少个节点？

\n

树中的节点总数，n = x（来自黄色部分）+ x（来自粉色部分）+ x（黄色部分下方最后一层的相加）= 3x

\n

你能注意到什么吗？作为副产品，左子树总共最多包含 2x 个节点，即2n/3个节点 (bcoz x = n/3)。

\n