n个元素堆的高度
Height of heap with n elements
我有以下问题：
"The height of a tree is the length of the longest branch of the tree. From the definition of height, what is the height of a heap with n elements? Give a clear and precise explanation with your answer."
堆=二叉树
我知道一棵完全二叉树的个数是2^(n° of levels - 1)
到目前为止，我尝试了以下方法：
如果存在三个堆（2个完全二叉树和1个非完全二叉树）使得：
- 堆A =是一棵完全二叉树，高度为H
- 堆 B = 是一棵二叉树，其高度比 A 多但比 C 少（所以高度与 C 相同 - 我认为？）
- 堆C = 是一棵高度为H + 1的二叉树
我可以说B的高度介于A和C的高度之间，B的元素个数介于2^(n° levels of A - 1) and 2^(n° levels of C - 1).
但是我不知道n个元素堆的高度是多少。
众所周知，堆是一棵完全二叉树。
让我们看一些堆：
我们可以看到：
如果堆有 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
我有以下问题：
"The height of a tree is the length of the longest branch of the tree. From the definition of height, what is the height of a heap with n elements? Give a clear and precise explanation with your answer."
堆=二叉树
我知道一棵完全二叉树的个数是2^(n° of levels - 1)
到目前为止，我尝试了以下方法：
如果存在三个堆（2个完全二叉树和1个非完全二叉树）使得：
- 堆A =是一棵完全二叉树，高度为H
- 堆 B = 是一棵二叉树，其高度比 A 多但比 C 少（所以高度与 C 相同 - 我认为？）
- 堆C = 是一棵高度为H + 1的二叉树
我可以说B的高度介于A和C的高度之间，B的元素个数介于2^(n° levels of A - 1) and 2^(n° levels of C - 1).
但是我不知道n个元素堆的高度是多少。
众所周知，堆是一棵完全二叉树。
让我们看一些堆：
我们可以看到：
如果堆有 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