阅读所有答案,我意识到混淆来自于对高度的精确定义。在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)
使用正确的高度定义,公式可以正常工作。