最坏的情况在MAX-HEAPIFY [英] worst case in MAX-HEAPIFY

问题描述

在 CLRS ，三版，第155页，这是因为在MAX-HEAPIFY，

In CLRS, third Edition, on page 155, it is given that in MAX-HEAPIFY,

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

我猜的原因是，在这种情况下，最大-Heapify具有向下浮动通过左子树。
但事情我不明白的是：为什么半满？
马克斯 - Heapify还可以向下浮动，如果左子树只有一个叶。那么，为什么不认为这是最坏的情况？

I guess the reason is that in this case, Max-Heapify has to "float down" through the left subtree.
But the thing I couldn't get is "why half full" ?
Max-Heapify can also float down if left subtree has only one leaf. So why not consider this as the worst case ?

推荐答案

阅读整个背景：

孩子们的子树分别具有大小至多2π/ 3 - 发生最坏的情况下，当该树的最后一行是正好一半满

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（最大NUM。在子树节点）+ O（1）

Since the running time T(n) is analysed by the number of elements in the tree (n), and the recursion steps into one of the subtrees, we need to find an upper bound on the number of nodes in a subtree, relative to n, and that will yield that T(n) = T(max num. nodes in subtree) + O(1)

在一个子树的节点数目的最糟糕的情况是，当最后一行是尽可能充分的一方，而空如可能在其他的。这就是所谓的半满。而左子树大小由 2N / 3 是有界的。

The worst case of number of nodes in a subtree is when the final row is as full as possible on one side, and as empty as possible on the other. This is called half full. And the left subtree size will be bounded by 2n/3.

如果你提出的情况下，只有几个节点，那么这是无关紧要的，因为所有的基础情况下，可以考虑 O（1）和忽略。

If you're proposing a case with only a few nodes, then that's irrelevant, since all base cases can be considered O(1) and ignored.

这篇关于最坏的情况在MAX-HEAPIFY的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！