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