logo标签列表

找出给定高度的n元堆的节点数

algorithm
7
我们在Thomas H. Cormen的问题中遇到了一个关于展示的问题。
我对这个问题感到困惑，如何会有至多enter image description here个节点。
例如，考虑以下问题： enter image description here 在上述问题中，在第2层有2个节点。但如果我们按照公式计算：
Greatest Integer of  (10/2^2+1) = 4

它不能满足Thomas H. Cormen的问题。

如果我错了，请纠正我。

提前感谢

不过这并不影响问题，但是你提出的树并不是一个堆。 - sepp2k
sepp2k，是的，应用子例程Heapify后，它将变成二叉堆。但是，我的问题不同，我正在询问高度为h的节点数有多少个。 - Nishant Kumar
10个回答
5
阅读所有答案，我意识到混淆来自于对高度的精确定义。在CLRS书的第153页中，高度定义如下：
将堆视为树，我们将堆中节点的高度定义为从该节点到叶子节点的最长简单向下路径上的边数...
现在让我们看一下Nishant提供的原始堆。节点8, 9, 10, 6和7位于高度0（即叶子）。节点4, 5和3位于高度1。例如，在节点5和其叶节点节点10之间有一个边。节点3和其叶节点节点6之间也有一个边。节点6看起来像是在高度1处，但实际上它在高度0处，因此是一个叶子。节点2是唯一一个在高度2处的节点。你可能会想知道节点1（根）距离节点6和7（叶子）有两个边缘，所以说节点1也在高度2处。但是，如果我们回头看定义，加粗的单词“longest”表明从根到叶子的最长简单向下路径有3条边（穿过节点2）。最后，节点1在高度3处。
总之，高度为0、1、2、3的节点分别有5个、3个、1个、1个。
让我们将公式应用于上面段落中的观察结果。我想指出，Nishant提供的公式是不正确的。
应该是 ceiling(n/2^(h+1))而不是ceiling(n/(2^h+1)。对于可怕的格式问题表示歉意。我还无法发布图像。
无论如何，使用正确的公式，
h = 0, ceiling(10/2) = 5 (节点8, 9, 10, 6和7)
h = 1, ceiling(10/4) = 3 (节点4, 5和3)
h = 2, ceiling(10/8) = 2 (节点2，但这没关系，因为公式预测高度为2的节点最多有2个。
h = 3, ceiling(10/16) = 1 (节点1)
使用正确的高度定义，公式可以正常工作。
4
在Tmh Corman中，我观察到他从1开始进行高度编号，而不是从0开始，因此公式是正确的，我进行了错误的解释。因此，对于上述问题，叶子的高度为1，根的高度为4。
3

看起来你的公式说高度为h的节点数目最多是[n/2^h+1]。在你的例子中，高度为2的节点只有两个，而这比你计算出的可能最大值4(左右)要少。

0

虽然Cormen中提到节点的高度是从节点到叶子节点所经过的最大距离（边数），但如果您将高度定义为节点到叶子节点的距离，即在叶子节点处高度为零，在根节点处高度为log(n)，则该公式仍然正确。

对于叶子节点，您有h=0；因此，根据公式n/(2^(h+1))，堆中叶子节点的最大数量将为n/2。

0
在计算Build-Max-Heap的紧密界限时，作者在方程式中使用了此属性。
在这种情况下，我们调用帮助程序Max-Heapify，它需要O(h)，其中h是以当前节点为根的子树的高度（而不是相对于完整树的节点本身的高度）。
因此，如果我们考虑以叶节点为根的子树，则其高度将为0，并且该级别的树中的节点数最多为n / 2 0+1 = n/2（即从叶节点形成的子树的h=0）。
同样，对于以实际根为根的子树，树的高度将为log(n)，在这种情况下，该级别的节点数将为1，即n / 2 logn+1的floor值=[n/n+1]。

0

那么高度1怎么办？Cormen的理论给出10 /（2 ^（1 + 1））= 3（向上取整），而在高度1处有4个节点。这是一个矛盾。

0

并不是说 Thomas H. Cormen 从1开始计算树的高度，实际上树的高度为 h = 0, 1, ..., log n，随着向上移动而增加：

enter image description here

而在下面的公式中，他加上了1以及高度：

enter image description here

所有的混淆都来自于这将与完美二叉树很好地配合使用，而不是你在问题中展示的那个，这就是为什么他说在大多数情况下。
当考虑大O时，实际上并不重要。
0

公式为

no. of nodes = n/(2^(h+1))

所以当h为2，且n = 10时

no. of nodes = 10/(2^(2+1)) = 10/(2^3) = 10/8 = 1.25

但是

ceil of 10/8 = 2

因此，从图中可以看到有2个节点。
-1

这个公式是错误的，在许多情况下都会给出错误的答案，比如在 h=1（即倒数第二层）的问题中，它给出的最大节点数为3，但实际上有4个节点。另外，让我们考虑一个有4个节点的树：

             a
            / \
           b   c
          /
         d

节点d的高度为0，让我们考虑使用公式n/2^(h+1)计算高度=1时的情况：

4/2^(1+1) = 1

这意味着此层最多只能有1个节点，但事实并非如此！

因此，这个公式是不正确的。

-1
公式是非常正确的。 公式没有任何问题！
让我们来看一下Nishant提出的问题中的树（虽然它还不是堆，但它是完整的）。 对于h = 0表示所有叶子，因此ceil（10 / 2 ^（0 + 1）= 5），因此有5个叶子 对于h = 1表示所有仅有一条弧线连接叶子的节点，因此ceil（10 / 2 ^（1 + 1））= 3，您的树中有3个这样的节点。 对于h = 2表示所有有两个连续弧线连接叶子的节点，因此ceil（10 / 2 ^（2 + 1））= 1，因此您只有一个这样的节点（根节点的左后继节点）。 对于h = 3表示所有拥有三个弧线连接叶子的节点，因此ceil（10 / 2 ^（3 + 1））= 1，即为根节点。
故事的寓意是你混淆了高度和级别。级别从上到下开始。这意味着你在第2级上有4个节点。也就是说，如果您从根开始并向下移动两个弧线，则可以到达4个节点。 而高度则完全不同。就像在上面的例子中，在高度为0时有5个节点（3个在第3级，2个在第2级）。因此，节点n的高度h表示您可以到达叶子的弧线数。
问候，

希望这能澄清问题。

来自巴基斯坦的Safdar

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接