compares for insert operation a binary heap

Question

When you use a binary heap to implement a priority queue ,it is stated that the insert operation requires at most 1+lg N number of compares.(lg N = log of N,to the base 2).

Consider the below picture ,

Here the tree has a maximum height of 3.Even if the node T was added to the bottom most level,it will only encounter a maximum 3 nodes including the root,when T swims up.That means ,there will only be 3 compares at most.

But the statement suggests that there will be a maximum of 1+lg 11 = 1+3 = 4 compares .

How is this possible? can someone please explain?

Answer 1

Think about what would happen if you inserted node B now. There can be up to four compares, for example:

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

Hope that answers your question.