爲什麼索引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）=日誌（1）= 0

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

所以你可以看到它的真實的情況下，n = 1

讓更換H =日誌（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'就會被取消。