algorithm - 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? -

this question came across in sedgewick's book. , on website, says answer 2, can't understand how achieve 2, because remove maximum need first exchange max element last one, decrease n, , sink last 1 down top place, takes logn exchanges. so, how achieve 2?

exchange & remove-max:

then need sink, l node, means need logn more exchanges.

here's example 15 nodes. idea is: have sons of root large (let left 1 larger), other left descendants smaller right ones. swap twice.

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

you'll switch 84, 100 99, 84 , you're done. 2 swaps.

for n > 3, after first swap, there no way neither of 2 sons of root won't larger new root (otherwise wasn't heap begin with). you'll have swap. author meant write swaps, not items.