The root node of a max-heap contains the largest value. Each child is smaller than the parent. We’ll start with the same array that we had in the previous few articles.
We’ll first construct the heap.
Next, we’ll start constructing the max-heap. Just like when we were constructing the min-heap, we’ll start with the 3rd node:
floor(6/2) = floor(3) = 3
Since 9 has only one child node, 9 will be compared to 3. If the parent is less than the child, the nodes will be swapped. Since 9 is larger than 3, the nodes are not swapped. We move to the 2nd node.
The 2nd node has two children. The larger of the two is 5, so 5 is compared with 2. Since 5 is larger than 2, the two values are swapped.
We’ll iterate through it once more to make sure that Max-Heap has been achieved. We’ll start with the 3rd node. Since the parent, 7, is larger than its child, the nodes are kept in place.
The comparison node is decremented and the 2nd node is compared with its children. Since the parent is larger than both of its children, the nodes remain in their current positions.
Since there are no changes to the tree, we can conclude that the max-heap tree has been created.
If you liked what you read, my book, An Illustrative Introduction to Algorithms, covers this data structure and many more.