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

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?

CodePudding user response：

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_₂