Why does it require no more than 1 + logN compares when inserting a new node into a heap?

Question

I think when inserting a new node into a heap, the amount of nodes it might passes by is logN, why is it (1 + logN), where is 1 from?

Because log(1) = 0 but inserting into a heap with 1 element takes a comparison — user555045
– user555045, Commented Feb 12, 2017 at 0:54
Thanks for your answer. I think this should be the correct answer. — user1888955
– user1888955, Commented Feb 12, 2017 at 2:19

Sergey Kalinichenko · Accepted Answer · 2017-02-12 01:14:58Z

2

This is necessary to account for the border case when the number of notes is 2ⁿ. A heap of n levels fits 2ⁿ-1 objects, so adding one more object starts the new level:

Black squares represent seven elements of a three-level heap. Red element is number eight. If your search takes you to the location of this last element, you end up with four comparisons, even though log₂8 is three.

answered Feb 12, 2017 at 1:14

Sergey Kalinichenko

729k85 gold badges1.2k silver badges1.6k bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

user1888955 Over a year ago

thanks for your answer But I don't understand why there are 4 comparisons. For me, it seems only 3 times even if the new added red square swims up to root (three comparisons: red line, green line and blue line, 3 times in total)

Sergey Kalinichenko Over a year ago

@user1888955 You need to compare to the root, root's child, root's grandchild, and the red node itself, to ensure that you have found the item that you are looking for.

user1888955 Over a year ago

Thank you for your quick reply :) i missed comparison on the node itself.

Collectives™ on Stack Overflow

Why does it require no more than 1 + logN compares when inserting a new node into a heap?

1 Answer 1

3 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Related