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?

Cadell

well, floor(n/2) doesn't mean the middle of the tree, but the number of nodes that aren't leaves. – Cuda

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).

Prestonprestress

Thank you very much. I still don't get the first paragraph you but as I understood: (Starting from (non-leaf) nodes is efficient since leaf nodes do not go down and thus saving the time takes crossing the leaves). Is this correct? – Cadell

@Medo Roughly speaking, yes. – Prestonprestress

shouldn't it go down by at most 1 in 4th line of the first paragraph? If so, should I edit it? – Unlearn

Answer 2

If we start the heapify process from the beginning (or root node) that would be wrong because the rest of the heap would not be a max heap so, we can't guarantee that the root node will be the highest node.

So it would make sense we start from the end. That is, bottom up approach makes sense.

But if we start from the end, then that means we're starting from the leaf nodes which will not go up (nothing to perform in heapify if we're calling on leaf nodes). So instead we start from a level above the leaf nodes and hence keep calling heapify for all the nodes from a level above leaf node to the root node.

The index of the parent node of the leaf node is nothing but n / 2 - 1 where n is the size of the array.

We can calculate this easily: The last child node or leaf node has the index of n - 1 so

c = n - 1

If p is the index of its parent node Then

c = 2 * p + 1
p = (c - 1) / 2

Substitute

c = n - 1
p = (n - 2) / 2
p = n / 2 - 1

Which is the floor of n / 2

Hope it makes sense now!

Jaxartes