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”就会被抵消。