Modified algorithm for building a Heap

Question

I am quite new to programming and I am trying to understand a certain problem regarding heap sort. In a book I'm reading, there is a modified algorithm for building a max heap, which is:

BuildHeap(A)
    A.heap-size = 1
    for i = 2 to A.length
        Heap-Insert(A, A[i])

So from my understanding, this algorithm takes in an array and defines the size of the heap to be 1 and then iterates from 2 to the total length of the array and then inserts the value into the heap.

But how would this build a max heap? If I had an array of [4, 7, 2, 3, 9, 1], then wouldn't the algorithm start at value 2 and then simply add all the values from the A[2] to A.length to the heap without actually building a max heap?

I do not understand how the heap-size = 1 does anything in the algorithm other than restrict the total size of the heap. I am confused as to how you would build a max heap.

From what it states in the book, the normal max heap works by first inserting every array value into a heap, and then starting at the A/2 place, then working backwards and swapping values that are larger than the current value being assessed by calling Max-Heapify.

So how would this max heap work since there is no Max-Heapify(A, largest) call, but instead there is simply a heap-insert(A, A[i])?

Heap-insert increases the size of the heap by one (A.length += 1) and ensures that the heap property is maintained by inserting the new element in the right place. — rici
If it increases the size of the heap by 1, then does it not just add the next value in the array to the heap without actually making it a max heap? So if the array was used above, wouldn't the array first start with the value 2, and then increase the heap by 1 and add 3 below the 2 in the heap? — learningtoprogram123
In pseudo code, it is often the habit to use 1-based indexing so A[2] is the second element in A, so that is the 7. — trincot
@trincot Correct me if I am wrong, but the algorithm first looks at the 2nd through last entry of the array and simply adds the largest? Does Heap-insert implicitly select that largest element of the array? I am simply trying to understand where in this small code does the actual selection of the largest element of the array happen. — learningtoprogram123
Well, the Heap-Insert routine does all the hard work of bubbling up the rightmost value in its correct position. Note that your title is misleading: this is not heapsort, but building a heap. — trincot

trincot trincot · Accepted Answer · 2020-09-14T16:50:39

First of all, this question is not about heap sort, which is just one of the applications for a heap. You are asking about the heap construction.

The pseudo code you presented is indeed an alternative (and less efficient) way of building a heap, and this would actually be the algorithm that many would come up with when they wouldn't have known about the standard algorithm of Floyd.

So taking a look at the code:

BuildHeap(A)
    A.heap-size = 1
    for i = 2 to A.length
        Heap-Insert(A, A[i])

Most of the logic of this algorithm is berried inside the Heap-Insert function, which is not just a simple "append" to an array: it does much more than that. Wikipedia describes that hidden algorithm as follows:

Add the element to the bottom level of the heap at the leftmost open space.

Compare the added element with its parent; if they are in the correct order, stop.

If not, swap the element with its parent and return to the previous step.

You write in your question:

there is no Max-Heapify(A, largest)

Indeed, it would be too simple if you already knew what the largest value was before using the heap. You need to first insert a value (any value) in a heap, and let the heap do its magic (inside Heap-Insert) to make sure that the largest value ends up in the first (top) position in the array A, i.e. in A[1].

The first step of the quoted algorithm is thus important: Heap-Insert expects the new value to be inserted at the end.

Let's work through the example [4, 7, 2, 3, 9, 1], and let's put a pipe symbol to indicate the end of the heap. At the start, the heap size is 1, so we have:

4 | 7   2   3   9   1

Let's also represent a more visually appealing binary tree at the right side -- it just has a root element:

4 | 7   2   3   9   1                  4

Then we call Heap-Insert(A, A[2]), which is Heap-Insert(A, 7). The implementation of Heap-Insert will increase the size of the heap, and put that value in the last slot, so we get:

4   7 | 2   3   9   1                  4
                                      /
                                     7

Heap-Insert has not finished yet -- this was just the first step it performs. Now it "bubbles up" that 7 following steps 2 and 3 of that quoted algorithm, and so we get:

7   4 | 2   3   9   1                   7
                                       /
                                      4

At the second iteration of the pseudo code loop, we call Heap-Insert(A, 2), so Heap-Insert performs its first step:

7   4   2 | 3   9   1                   7
                                       / \
                                      4   2

...and finds out that nothing needs to change when performing step 2 and 3.

We continue inserting 3:

7   4   2   3 | 9   1                   7
                                       / \
                                      4   2
                                     /
                                    3

...and again nothing needs to change as 3 is less than 4 (remember that A[2] is the parent of A[4].

We continue inserting 9:

7   4   2   3   9 | 1                   7
                                       / \
                                      4   2
                                     / \
                                    3   9

And here 9 > 4, and also 9 > 7, so Heap-Insert will further modify A to this:

9   7   2   3   4 | 1                   9
                                       / \
                                      7   2
                                     / \
                                    3   4

One more to go:

9   7   2   3   4   1                   9
                                      /   \
                                     7     2
                                    / \   /
                                   3   4 1

And Heap-Insert has nothing more to do as 1 < 2.

Modified algorithm for building a Heap

1 Answers