We’ll look at two types of heaps: max-heap and min-heap. The root node (top-most node) of a min-heap contains the smallest value. Each child is larger than the parent. Once the heap was built in the previous example, a min-heap can be constructed from it. To build a min-heap, we’ll start from the floor(n/2) node. The reason for the floor is due to uneven number of nodes. If the number of nodes was 7, the starting position would be at floor(7/2) = floor(3.5) = 3.

For our example, there are 6 nodes: floor(6/2) = floor(3) = 3

The starting position will be at the third node. We’ll check to see if there is a child node that has a smaller value than 9. Since there is, the two nodes are swapped.

 

 

We’re done with the 3rd node and we move to the node before, node 2. At node 2, there are two children. A comparison is made between the two children and the smallest node is selected, in this case node 4. Next, 2 is compared to 4. Since 2 is already smaller than 4, the nodes are left in place.

 

 

We’re done with the 2nd node and we move to the node before, node 1. At node 1, there are two children. A comparison is made between the two children and the smallest node is selected, in this case the node with the value of 2.

 

 

Next, 7 is compared to 2. Since 2 is smaller than 7, the nodes are swapped.

 

 

Now that we have reached the root node, we must iterate through the heap once more to see if we finished generating a min-heap. So, we’ll repeat the procedure again. We begin at the third node.

 

 

Since 3 is already smaller than 9, we can move to the 2nd node. A comparison is made between the two children. Since 4 is smaller, 7 is compared to 4.

 

 

Since 4 is smaller than 7, the two nodes are swapped. The comparison node moves from the second node to the first node.

 

 

A comparison is made between the two children. Since 3 is smaller, 2 is compared to 3. The first node is already smaller, so the nodes remain in their current positions.

One final iteration needs to occur to verify that the min-heap is created. We start back at the third node. Since the third node doesn’t have any children that are smaller than itself, we move to the second node. Similarly, the second node doesn’t have any children that are smaller than it. We finally move back to the first node and verify that the first node also doesn’t have any children that are smaller than it. The min-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.