The reason of calling heapify from the middle of the array when building a heap

Question

When building the heap, we start calling max_heapify(A,i) from the middle of the tree, i.e. floor(n/2), until the root in decreasing fashion to maintain heap property. I've read some reasons behind this but I still don't understand why. Kindly, can someone explain the reason of that?

Thank you.

Answer 1

If we do it this way, the time complexity is linear in the worst case (the idea of the proof is to observe that when an element is sifted down, another element moves up and element can never go down once it has been moved up. Thus, the number of times each leaf goes down is zero, the number of time each element one level above the leaves goes up is at most 1 and so on. If we compute this sum explicitly, it turns out to be O(N)).

If we start from the end and sift elements up the time complexity is O(N log N) (for example, if the array is reversed).

To sum up, this way is more efficient.

Note: we could have started from the last element, but a leaf can never go down anyway, so it would be useless (the time complexity would stay linear, though).