heap - インデックス i (1 から始まる) のヒープ ノードとその高さ h が (2^h)*i <= n < (2^(h+1)*i) を満たすのはなぜですか? n はヒープ サイズです。

Question

インデックス i (1 から始まる) のヒープ ノードとその高さ h が (2^h)*i <= n < (2^(h+1)*i) を満たすのはなぜですか? n はヒープ サイズです。

Answer 1

ケース N:1

2^h <= 1 <= 2^(h+1)

ノードの高さが log(n) = log(1) = 0 であることに注意してください

= 2^0 <= 1 <= 2^(0+1) 
= 1 <= 1 <= 2

したがって、n = 1 の場合に真であることがわかります。

h = log(n) を元の質問に置き換えてみましょう

= 2^h <= n <= 2^(h+1)
= 2^(log(n)) <= n <= 2^(log(n)+1)   #replace n = log(n)
= n <= n <= 2^log(n) * 2^1   #exponents property
= n <= n <= 2n

各辺を「i」で割ると、インデックス「i」が相殺されることに注意してください。