How come inserting a node in a heap takes 1+lgN compares. From where did that 1 came from?

Question

Here, 91 is being added to the heap, so 91 will be compared with 36 then with 89 and finally with 90 so total compares are 3 = lg8. So what was the reason of adding 1 in utmost number of compares when you are inserting an element in the heap?

Answer 1

To verify the claim, the exact context is crucial, but the edge case can be explained as follows:

Before insertion of node 91, the binary heap is perfect:

        __90__
       /      \
     89        70
    /  \      /  \
  36    75  63    65

It has 7 nodes, so N is 7. The floored base-2 logarithm of N is 2 in this case.

When inserting 91, there are 3 comparisons needed to restore the heap property. So in this particular case we have that the number of comparisons is indeed 1+_⌊log₂𝑁_⌋. This is a worst case scenario, and assumes that 𝑁 is the number of nodes before insertion takes place.

If 𝑁 is defined as the number of nodes after the insertion, or the original tree is not perfect, then the additional 1 is not needed in that formula.