algorithm - 二叉堆：以位置 i 为根的子树的高度

Question

给定 n 个值，我创建了一个二进制最大堆。我想知道计算以任何位置 i 为根的子树高度的公式。

Answer 1

任何节点在位置的级别k是floor(log2(k + 1))。

所以以 positioni为根的子树的高度就是层级差（假设单个叶子的高度为 0）：height = floor(log2(n + 1)) - floor(log2(i + 1))：.

我们需要检查子树是否到达堆的底部，或者它是否短了一层。我们通过比较最左边的叶子和最后一个元素来做到这一点：

if(pow(2, height) * (i + 1) - 1 >= n)
    height--;

Answer 2

简单的算法：- 向左走，直到你命中 null。这可以通过在二进制堆中完成left = 2*parent。算法的时间复杂度为O(logn)。此外，您可以使用以下不等式直接评估它：- 2^k*i < N , k < log2(N/i) , k = log2(floor(N/i))。在O(log(log(n)))需要对floor(N/i).

查找以整数设置的最高位：-

high = 63
low = 0
mid = 0
while(low<high) {

  mid = (low+high)>>1
  val = 1<<mid
  if(val==mid)
    return mid
  if(val>mid) {
     high = mid-1
  }
  else low = mid+1
}

return mid

Answer 3

完全二叉堆中的每一层都有 2^i 个节点，因此任何二叉堆在层 (i) 中必须有 2^i 个节点，除了最后一层。

..............................(100)...................  2^0 nodes
............................./.....\..................  
...........................(19)...(36)................  2^1
........................../...\.../...\...............
.......................(17)..(3).(25).(1).............  2^2
......................./..\...........................
.....................(2).(7)..........................  last level.

因为最后一个级别可能不完整所以n < 2^h