二进制堆高度
Binary Heap Height
在具有 N 个节点且高度为 h 的二叉堆中：
1 + 2^1 + 2^2 + … + 2^(h-1) + 1 <= N <= 1 + 2^1 + 2^2 + … + 2^(h-1) + 2^h
2^h <= N < 2^(h+1)
h <= log2(N) < h+1
最后一行：
第一个不等式意味着 h 是 O(log N)。
但是为什么第二个不等式意味着 h 是 Ω(log N) 呢？
如果是“log2(N) < h”，我会理解，但我的问题是“h+1”中的“1”。
从第二个不等式，你有
h + 1 > log(N) ↠ h > log(N) - 1,
因此，
h = Ω(log(N) - 1).
然而，
log(N) - 1 = Θ(log(N)),
你可以使用传递规则
f(N) = Ω(g(N)) 和 g(N) = Θ(h(N))意味着 f(N) = Ω(h(N)).
在具有 N 个节点且高度为 h 的二叉堆中：
1 + 2^1 + 2^2 + … + 2^(h-1) + 1 <= N <= 1 + 2^1 + 2^2 + … + 2^(h-1) + 2^h
2^h <= N < 2^(h+1)
h <= log2(N) < h+1
最后一行：
第一个不等式意味着 h 是 O(log N)。
但是为什么第二个不等式意味着 h 是 Ω(log N) 呢？
如果是“log2(N) < h”，我会理解，但我的问题是“h+1”中的“1”。
从第二个不等式，你有
h + 1 > log(N) ↠ h > log(N) - 1,
因此，
h = Ω(log(N) - 1).
然而，
log(N) - 1 = Θ(log(N)),
你可以使用传递规则
f(N) = Ω(g(N)) 和 g(N) = Θ(h(N))意味着 f(N) = Ω(h(N)).