N元素堆的高度
N元素堆的高度
提问于 2019-04-18 21:27:06
我有以下问题：
“树的高度是树的最长树枝的长度。从高度的定义来看，有n个元素的堆的高度是多少?用你的答案给出一个清晰而准确的解释。”
堆=二叉树
我知道一个完整二叉树的数目是2^(级别的n°)。
到目前为止，我尝试了以下几点：
如果有三个堆(2个完整的二叉树和1个非完整的二叉树)，那么：
- 堆A=是一棵高度为H的完整二叉树。
- 堆B=是一个二叉树，它的节点比A多，但小于C(所以它的高度与C相同-我认为？)
- 堆C=是高度为H+1的二叉树。
可以说，B的高度介于A和C的高度之间，B的元素数介于2^(A-1的n°能级)到2^(C1的n°水平)之间。
但是，我不知道如何使用n个元素的堆的高度。
回答 2
Stack Overflow用户
回答已采纳
发布于 2019-04-19 05:54:48
如您所知，堆是一个完整的二叉树。
让我们来看看一些堆：
我们可以看到：
- 如果堆有一个节点，那么它的高度将是1
- 如果堆有2到3个节点，那么它的高度将是2
- 如果堆有4到7个节点，那么它的高度将是3
- ..。
- 如果堆从2^i到2^(i+1) -1节点，那么它的高度将是i。
注意，只有当我们用节点填充某个级别并启动一个新级别时，堆的高度才会增加。
这只发生在节点上: 1，2，4，8，16，32，.
因此，具有n个节点的堆将具有高度层(log2(N))+1
Stack Overflow用户
发布于 2022-09-30 07:20:14
计算元素总数
def height(self):
return math.floor(math.log(n,2))+1页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/55753942
复制相关文章
相似问题
腾讯云开发者
