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?
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.