algorithm - バイナリ ヒープ: 位置 i をルートとするサブツリーの高さ

Question

n 値を指定して、Binary Max-Heap を作成しました。任意の位置 i を根とする部分木の高さを計算する式を知りたいです。

Answer 1

完全なバイナリ ヒープの各レベルには 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

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

位置のノードのレベルkは ですfloor(log2(k + 1))。

したがって、位置をルートとするサブツリーの高さは、iレベルの差です (単一の葉の高さが 0 であると仮定します): height = floor(log2(n + 1)) - floor(log2(i + 1)).

サブツリーがヒープの最下部に達しているかどうか、または 1 レベル短いかどうかを確認する必要があります。これを行うには、一番左のリーフを最後の要素と比較します。

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