Visually Explained Algorithms
Now that we know how to create a max-heap, we’ll move into sorting an array of values using heap sort. To sort the array using heap sort, we’ll keep creating max-heaps. Each time a max-heap is created, the root is removed and is considered sorted. Let’s start with the following example.
The first step is to construct a tree from the array.
We’ll follow the same procedure as outlined in my other article, Constructing Max-Heap from a Tree. To begin, 5 is swapped with 9 and then 5 is swapped with 7 to generate a max-heap.
Considering that the tree is just a visual representation of the array, I’ll show you what the array looks like after the initial max-heap sort.
The root node is swapped with the last item in the array. The last item is now sorted and is removed from the tree.
A new heap is created. The root node is swapped with the largest of its children, which is 7, and a new max-heap is constructed.
The root node is swapped with the last node in the tree and is removed from the tree. We now have two nodes that are sorted: 7 and 9.
We create the new max-heap by swapping 1 with the largest of its children, which is 5.
Since the new max-heap has been created, the root node is swapped with the last element in the tree, which is 2. Number 5 is now sorted.
The process continues by swapping 2 with the largest of its children, 3, achieving max-heap.
The root node is swapped with the last element effectively sorting element 3.
The procedure is done one more time. The root node is swapped with the largest of its children, 2, creating a max-heap.
The root node is swapped with the last node sorting element 2.
Since there’s only one element left in the array, that element is marked as sorted and so is the array.
This completes the heap sort process.
If you liked what you read, my book, An Illustrative Introduction to Algorithms, covers this Algorithm and many more.