Why we build max heap from bottom up instead from top bottom

Question

Question: Why do we want the loop index i in line 2 of BUILD-MAX-HEAP to decrease from ⌊length[A]/2⌋ to 1 rather than increase from 1 to ⌊length[A]/2⌋?

Algorithms: (Courtesy Introduction to Algorithms book):

I tried to show this using drawings as follows.

Approach 1: if we apply build heap the opposite way from 1 to ⌊length[A]/2⌋ of array A = <5,3,17,10,84>, we would have:

Approach 2: if we apply build heap the opposite way from ⌊length[A]/2⌋ and decrease to 1 of array A = <5,3,17,10,84>, we would have:

Problem: I see that in both cases the heap property that parent is larger than its children is maintained, so I don't see why a solution says that there would be a problem such that, "we won't be allowed to call MAX-HEAPIFY, since it will fail the condition of having the subtrees be max-heaps. That is, if we start with 1, there is no guarantee that A[2] and A[3] are roots of max-heaps."

MAX-HEAPIFY takes advantage of the fact that the LEFT and RIGHT are both valid heaps. If you start with `i=1`, then that assumption is not valid. After MAX-HEAPIFY(A, 1), the value in A[1] is either A[1], A[2], or A[3], and the value is never changed by any future iteration. But the largest value in the heap might not have been one of the first three. In your example, the first MAX-HEAPIFY(A, 1) produces <17,3,5,10,84>, and nothing changes A[1] after that, so the root is 17. I don't know how 84 managed to get there in your Approach 1 diagram. — Raymond Chen, Aug 25 '21 at 13:29
@RaymondChen. Very clear answer. I assumed that I insert array in real time, so I Heapify each time I insert a new element each time I add a new element, which is basically same as you said, so I did not realize I was doing Heapify Up approach in approach 1. In second approach, I did Heaify after I inserted all elements. So both are based on fact of Heapify Up, so I did not even follow Heapify down that is asked in the question. — Avv, Aug 25 '21 at 13:44
If you are inserting the elements one at a time, then that's a different algorithm. BUILD-MAX-HEAP is for creating a heap from a non-heap array. If you want to add a single element to an already-valid heap, that is a different operation, probably called something like INSERT-HEAP. Adding an item one at a time is [discussed here](https://stackoverflow.com/questions/36226714/why-is-the-top-down-approach-of-heap-construction-less-efficient-than-bottom-up). — Raymond Chen, Aug 25 '21 at 17:49

score 3 · Accepted Answer · answered Aug 25 '21 at 14:17

The thing is that you can only rely on MAX_HEAPIFY to do its job right, when the subtree that is rooted at i obeys the heap property everywhere except possibly for the root value (at i) itself, which may need to sift down. The job of MAX_HEAPIFY is only to move the value of the root to its right position. It cannot fix any other violations of the heap property. If however, it is guaranteed that the rest of the tree below i is obeying the heap property, then you can be sure that the subtree at i will be a heap after MAX_HEAPIFY has run.

So if you would start with top node, then who knows what you will get... the rest of the tree is not expected to obey the heap property, so MAX_HEAPIFY will not (necessarily) deliver a heap. And it doesn't help to continue the work in a top-down fashion.

If we take the example tree and perform the forward loop alternative, then we start with a call of MAX_HEAPIFY(1) on this tree:

...then 5 would swap with 17 (at position 3), and then we would call MAX_HEAPIFY(3) recursively on that node, which would do nothing. So we would get:

Next, we call MAX_HEAPIFY(2) which will swap 3 with 84:

Again a recursive call follows on the node with value 3, but that will not do anything.

This was the last call of MAX_HEAPIFY in the forward loop alternative... and we can see that the value 84 had no chance to find its way all the way to the top where it belongs.

Very detailed and clear answer, thank you. – Avv Aug 25 '21 at 14:19 — Avv, Aug 25 '21 at 14:19

Why we build max heap from bottom up instead from top bottom

1 Answers1