Insertion into a Binary Heap: Number of exchanges in worst case

Question

I was going through Cormen's 'Algorithms Unlocked'. In chapter 6 on shortest path algorithms, on inserting data into a binary heap, I find this: "Since the path to the root has at most floor(lg(n)) edges, at most floor(lg(n))-1 exchanges occur, and so INSERT takes O(lg(n)) time." Now, I know the resulting complexity of insertion in a binary heap is as mentioned, but about the number of exchanges in the worst case, should it not be floor(lg(n)) instead of floor(lg(n))-1. The book's errata says nothing regarding this. So I was wondering if I missed something.

Thanks and Regards, Aditya

Answer 1

floor(lg(n)) is the correct expression for the maximum number of edges on a path between a leaf and the root, and when you do swaps, you may end up doing one swap for each edge. So floor(lg(n)) is the correct answer for the worst-case number of swaps. The author most likely confused the number of edges on the path with the number of VERTICES on the path when they were writing. If you have V vertices on the path between the leaf and the root, then V-1 is the number of edges so V-1 is the number of swaps you might do in the worst-case.

Answer 2

You can easily show that it's floor(lg(n)). Consider this binary heap:

    3
  5  7

To insert the value 1, you first add it to the end of the heap:

    3
  5  7
1

So there are 4 items in the heap. It's going to take two swaps to move the item 1 to the root. floor(lg(4)) is equal to 2.