A heap is a complete binary tree that can be either a max-heap or a min-heap. The max-heap has the property that the key value of any node must be greater than or equal to the key values of its children. In the min-heap, the key value of any node must be lower than or equal to the values of its children.
In this recipe, we will learn to create a max-heap of the following list of integers:
| 5 | 2 | 9 | 3 | 1 | 4 | 6 |
In this heap sort method, the binary tree is constructed in the form of an array. In heap sort, the values in the array are added one by one, keeping the max-heap property true (that is, the key value of any node should be larger than or equal to its children). While adding the elements of the array, we keep track of the key value of the parent node with (x-1)/2, where x is the element whose parent is to be found. If the element inserted in the heap is larger than the key value of its parent, then interchanging takes place. For example, suppose the first key value entered is 5 (it is considered as the root); it is stored as the first element of the array, that is, heap[0]:
Then 2 is added to it as a left child. The first child will always be added to the left. When another value is entered, it is entered at the location of heap[1]. After insertion, its parent node location is computed with (x-1)/2, where x is 1. So, the parent comes out to be location 0. So, heap[1] is compared with its parent element, heap[0]. If the key element of the parent element, heap[0], is larger than heap[1], then we move further; else, we interchange their key values. In our example, the second element is 2, so no interchanging is required:
Now, we move to enter the third element. The third element is 9, and it is added as a right child of node 5 (see Figure 9.33 (a)). In the array, it is stored at the location of heap[2]. Again, its parent element location is computed by (x-1)/2, which again comes out to be 0. In keeping the property of max-heap (that the value of the parent node should be larger than or equal to its children), we compare the key values of the heap[0] and heap[2] elements. Because heap[0] is less than heap[2], it is violating the max-heap property. Thus, the key values of heap[0] and heap[2] will be interchanged, as shown in Figure 9.33(b):
Then 3 is added as a left child of node 2, as shown in Figure 9.34(a). In the array, the new value is inserted at the index location of heap[3]. Again, its parent element location is computed using the formula (x-1)/2, where x represents the index location where new value is inserted, that is, 3. The parent element location is computed as 1. In keeping with the property of max-heap, heap[1] must be larger than or equal to heap[3]. But because heap[1] is less than heap[3], it is violating the max-heap property. Thus, the key values of heap[1] and heap[3] will be interchanged, as shown in Figure 9.34(b):
Now, 1 is added as the right child of node 3. In the array, the new value is inserted at the index location of heap[4]. Because the property of max-heap is still maintained, no interchanging is required:
The next value is 4, which is added as the left child of node 5. In the array, the new value is inserted at the index location of heap[5]. Again, the property of max-heap is maintained, so no interchanging is required:
Next, 6 is added as the right child of node 5 (see Figure 9.37 (a)). In the array, it is inserted at the index location of heap[6]. Again, its parent element location is computed using the formula (x-1)/2. The parent element location is computed as 2. In keeping with the property of max-heap, heap[2] must be larger than or equal to heap[6]. But because heap[2] is less than heap[6], it is violating the max-heap property; so the key values of heap[2] and heap[6] will be interchanged, as shown in Figure 9.37(b):
Once the max-heap is made, we perform heap sort by repeating the following three steps:
- Removing its root element (and storing it in the sorted array)
- Replacing the root element of the tree (array) by the last node value and removing the last node (decrementing the size of the array)
- Reshuffling the key values to maintain the heap property
In the following Figure 9.38(a), you can see that the root element, that is, 9, is deleted and is stored in another array called arr. The arr array will contain the sorted elements. The root element is replaced by the last element of the tree. The last element of the tree is 5, so it is removed from the heap[6] index location and is assigned to the root, that is, at heap[0]. Now, the property of heap is no longer true. So, the values of node elements 5 and 6 are interchanged (see Figure 9.38(b)):
Now the process is repeated again, removing the key element of the root node and replacing its value with the last node and reshuffling the heap. That is, the root node element 6 is removed and is assigned to the sorted array, arr. And the root node is replaced by the last element of the tree that is by 4 (see Figure 9.39(a)). By putting the value 4 at the root, the property of heap is no longer true. So to maintain the property of heap, the value 4 is brought down that is the values of node elements 4 and 5 are interchanged, as shown in Figure 9.39(b)):
The steps are repeated to get the array sorted in descending order, as follows:
The program is compiled using GCC using the following statement:
gcc heapsort.c -o heapsort
Because no error appears on compilation, this means the heapsort.c program has successfully been compiled into the heapsort.exe file. On executing the file, it will ask us to specify how many numbers there are to be sorted. Following this, the program will prompt us to enter the numbers to be sorted. After entering the numbers, they will appear sorted in descending order, as shown in the following screenshot:
Voilà! We have successfully arranged numbers in descending order using heap sort.