What is the minimum number of items that must be exchanged during a remove the maximum operation in a heap of size N with no duplicate keys?

Question

This question I came across in Sedgewick's book. And on his website, he says that the answer is 2, however I can't understand how to achieve 2, because to remove maximum we need to first exchange the max element with the last one, decrease N, and then sink the last one down from the top into its place, which takes logN exchanges. So, how do you achieve 2?

Exchange & remove-max:

Then we need to sink, that L node, which means we need do logN more exchanges.

Answer 1

Here's an example for 15 nodes. The idea is: have the sons of the root be large (let the left one be larger), but the other left descendants be much smaller than the right ones. Then you will only swap twice.

                 100
       99                   90
   9       8            89      88
7    6   5   4        87   86   85   84

You'll switch 84, 100 then 99, 84 and you're done. Two swaps.

For n > 3, after the first swap, there is no way neither of the two sons of the root won't be larger than the new root (otherwise it wasn't a heap to begin with). So you'll have to do another swap. The author most likely meant to write swaps, not items.