Understanding Heap Sort

Dry Run Heap Sort

Step 1: Extract the root (14, swap it with (5) which is the last element in the heap and perform heapify at root (5) to get the below arrangement as shown in Step 1 diagram

Step 2: Extract the root (12), swap it with (3) which is the last element in the heap and perform heapify at root (3) to get the below arrangement as shown in Step 2 diagram.

Note: The nodes circled with green are not a part of the heap because we extracted them in the previous iterations. Hence, the green nodes form the sorted array. The red nodes in the array are unsorted.

hps1

Step 3: Extract the root (10), swap it with (2) which is the last element in the heap and perform heapify at root (2) to get the below arrangement as shown in Step 3 diagram

Step 4: Extract the root (9), swap it with (3) which is the last element in the heap and perform heapify at root (3) to get the below arrangement as shown in Step 4 diagram.

hps2

Step 5: Extract the root (8), swap it with (5) which is the last element in the heap and perform heapify at root (5) to get the below arrangement as shown in Step 5 diagram

Step 6: Extract the root (7), swap it with (2) which is the last element in the heap and perform heapify at root (2) to get the below arrangement as shown in Step 6 diagram.

 

hps3_1

Step 7: Extract the root (6), swap it with (3) which is the last element in the heap and perform heapify at root (3) to get the below arrangement as shown in Step 7 diagram

Step 8: Extract the root (5), swap it with (2) which is the last element in the heap and perform heapify at root (2) to get the below arrangement as shown in Step 8 diagram.

hps4

Step 9: Extract the root (4), swap it with (3) which is the last element in the heap and perform heapify at root (3) to get the below arrangement as shown in Step 9 diagram

Step 10: Extract the root (3), swap it with (2) which is the last element in the heap and perform heapify at root (2) to get the below arrangement as shown in Step 10 diagram.

hps5

At this moment only one element is left in the max heap and the array is sorted.

Note: The heapify step is not shown in the diagrams above, you can use a pen and a paper to work out the heapify step or may be you can refer to the first post in the heaps tutorial.