We looked at the construction of the min-heap tree from an already constructed tree. Min-heap can also be constructed directly from an array. If we look at the array that we used in the Creating a Heap from an Array article, we’ll see how easy it is to construct a min-heap from the array.

We start by adding the first node, 7.

Heaps are built from left to right. The next element that’s added is 2.

Since we’re constructing a min-heap, all the children nodes must be smaller than the parent node. Number 2 is smaller than 7, so the two nodes are swapped.

Next, element 9 is added. Since 9 is larger than 2, no swapping is necessary.

Next, element 4 is added.

Since 4 is smaller than 7, the two nodes are swapped.

Element 4 is then checked with element 2 to make sure it’s not smaller. Since it’s not, the elements remain in their current positions. Next, element 5 is added. Since element 4 is already smaller than element 5, the nodes remain in their current positions.

Finally, element 3 is added.

Since element 3 is smaller than element 9, the two nodes are swapped.

Element 3 is also compared to element 2. Since element 3 is larger than element 2, the two nodes remain in their current positions. There are no additional array elements. This completes the construction of the min-heap tree.

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


Leave a Reply