Why we should use sink to construct the heap in heapsort rather than swim?

Question

In 《Algorithms 4th edition》 2.4. It mentioned that In heap construction, to proceed from right to left, using sink() to make subheaps is more efficient. But why?

I think it is the same to proceed from left to right, using swim()

Answer 1

For example, let's say the heap has 7 elements, and the code starts from the left using swim(). The first element can be skipped. It's already at the top. The second element may need to move up one level. Same for the third element. Elements 4 thru 7 may need to move up two levels. Worst case compare/swap count is 2*1 + 4*2 = 10. In general, it takes O(nlogn) time.

Now consider starting from the right and using sink(). The last 4 elements can be skipped. They're already at the bottom. The second and third elements may need to move down one level. The first element may need to move down two levels. Worst case compare/swap count is 2*1 + 2 = 4, and in general the time is O(n).

In short, heapifying an array with sink() is faster than swim() by a factor of O(logn).