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

Question

我们在Thomas H. Cormen遇到了一个 要求展示的问题

在这里,我对这个问题感到困惑,即大多数节点将会如何

例如,考虑这个问题:

在高度2的上述问题中,有2个节点.但是如果按公式计算:

Greatest Integer of  (10/2^2+1) = 4 

它不符合Thomas H. Cormen的问题.

如果我错了,请纠正我.

提前致谢

Answer 1

阅读所有答案，我意识到混乱来自于高度的精确定义。在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 处。但是如果我们回顾一下定义中，粗体字“最长”表示从根到叶子的最长简单向下路径有 3 条边（经过节点 2）。最后，节点 1 的高度为 3。

综上，高度为0、1、2、3的节点分别有5、3、1、1个。

让我们将该公式应用于我们在上一段中所做的观察。我想指出的是，Nishant给出的公式是不正确的。

它应该是天花板(n/2^(h+1))而不是天花板(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，天花板（10/16）= 1（节点 1）

有了正确的高度定义，这个公式就有效了。

Answer 2

看起来你的公式说最多有[n/2^h+1] 个高度为 h 的节点。在您的示例中，有两个高度为 2 的节点，该节点小于计算出的可能最大值 4(ish)。