高度H堆中的元素最小和最大数量是多少？

Question

我遇到了这个问题：

高度堆中的元素的最小和最大数量 $ h $ ？

我想出了这个理论： $$ \ sum_ {i= 0} ^ {h-1} 2 ^ i= 2 ^ h-1 $$

$ 2 ^ h-1 $ 是内部节点，据了解了理解的事实。但是因为除了CLRS提到的堆是一个几乎完全二叉树之外，它无处不在它被提到它是一个完整的二叉树。

可以轻松计算最大元素数： $$ \ sum_ {i= 0} ^ {h} 2 ^ i= 2 ^ {h + 1} -1 $$

但我无法获得计算最小元素数量的点： 应该是： $$ 2 ^ {h} +1 $$ for $ 0 $ 或 $ 2 $ 儿童属性

或者应该是： $$ 2 ^ {h} $$ for $ 0 $ 或 $ 1 $ 儿童属性

参考1： https://walkccc.github.io/clrs/ Chap06 / 6.1 /＃61-1

参考2： heapsort

谢谢。

Answer 1

高度 $ h $ 在深度 $ h-1 $ 并且需要至少有一个节点 $ h $ 。

因此，节点的最小总数必须至少为 $ \ sum_ {i= 0} ^ {h-1} 2 ^ i + 1= 2 ^ {h} -1 + 1= 2 ^ h。 $ ，由于堆与 $ 2 ^ h $ 节点具有高度 $ h $ 。