data-structures - n 个元素的堆的高度

Question

我有以下问题:

“树的高度是树的最长分支的长度。从高度的定义来看，一个有n个元素的堆的高度是多少？用你的答案给出一个清晰准确的解释。”

堆=二叉树

我知道完整二叉树的数量是 2^(n° of levels - 1)

到目前为止，我尝试了以下方法:

如果有 3 个堆(2 个完全二叉树和 1 个非完全二叉树)，使得:

堆 A = 是一个完全二叉树，高度为 H

堆 B = 是一个高度二叉树，其节点比 A 多但小于 C(所以与 C 高度相同 - 我认为？)

堆 C = 是高度为 H + 1 的二叉树

我可以说 B 的高度介于 A 和 C 的高度之间，B 的元素数介于 2^(n° A - 1 级) 和 2^(n° C - 1 级) 之间。

但我不确定如何确定具有 n 个元素的堆的高度。

Answer 1

众所周知，堆是一棵完整的二叉树。

让我们看看一些堆:



我们可以看到:

如果堆有 1 个节点，它的高度将为 1

如果堆有 2 到 3 个节点，它的高度将为 2

如果堆有 4 到 7 个节点，它的高度将为 3

...

如果堆有从 2^i 到 2^(i+1) - 1 个节点，它的高度将为 i

请注意，只有当我们用节点填充某个级别并开始一个新的级别时，堆的高度才会增加。

这只发生在节点上:1, 2, 4, 8, 16, 32, ...

因此，具有 n 个节点的堆将具有高度 floor(log2(n)) + 1