Let’s use the same array that we used to construct the min-heap to create the max-heap from an array.

We start by adding the first node, 7.

We move top-to-bottom, left-to-right and we add the 2nd node, 2.

Since 7 is larger than 2, the nodes remain in their current position. Next, 9 is added to the heap.

Since 9 is larger than 7, the two nodes are swapped.

Next, 4 is added as a child of 2.

Since 4 is larger than 2, the two nodes are swapped.

We observe that 4 moved up, so 4 is also compared to 9. Considering that 4 is smaller than 9, they’re kept in place. The next value to be added is 5.

Since 5 is larger than 4, the two values are swapped.

Since 5 moved up, 5 is compared to 9. Seeing that 5 is smaller than 9, we’ll keep the two values in place. Finally, 3 is added.

Considering that 3 is smaller than 7, the two values remain in their positions. This completes the construction of the Max-Heap from an array.

If you liked what you read, my book, An Illustrative Introduction to Algorithms, covers this Algorithm and many more.


Leave a Reply