algorithm - 比较二叉堆的插入操作

Question

使用二叉堆实现优先级队列时，说明插入操作最多需要 1+lg N 次比较。（lg N = log of N，以 2 为底）。

考虑下图，

这里树的最大高度为3。即使将节点T添加到最底层，当T向上游时，它也只会遇到包括根在内的最多3个节点。也就是说，只会有3次比较最多。

但该声明表明最多会有 1+lg 11 = 1+3 = 4 compares 。

这怎么可能？有人可以解释一下吗？

Answer 1

想想如果你现在插入节点 B 会发生什么。最多可以有四个比较，例如：

B<E? B<G? B<S? B<T?

希望这能回答你的问题。