Heapsort

Imagine you have built a device with a limited amount of memory full of data, and you are required to sort them to function the device. The algorithm that will rescue you here is the heapsort algorithm. This algorithm doesn't require any extra memory other than the memory needed to store your data. Not only will the algorithm save your device's memory, but also it will provide moderately high and consistent performance. Yet, it is easy to learn and implement.

General words about heapsort

Heapsort is a comparison-based sorting algorithm that uses the properties of a binary heap to extract sorted numbers from an array. Binary heap has two types: max-heap and min-heap. Max-heap has the maximum number, and min-heap has the minimum number at its root. So, our strategy is to recursively extract the maximum (max-heap) or minimum number (min-heap) from the root of a binary heap and store them in an array. But pulling the root element from a binary heap will destroy its heap property. So we also have to heapify the structure after each step of extraction. Although this sorting method is not as fast as several others, it requires no additional memory other than your input data. For this reason, heapsort is very consistent with its performance.

Setup and terminology

Let's learn about heapsort by sorting array A in ascending order, which has ten elements. For convenience, we choose the index of the first element to be 1.

Here is the complete binary tree representation of the array.

We prepare the binary tree from the array by putting elements level by level from left to right. Level 1 contains only the root element, which is the first element of the array. It has two children, resides on level 2. They are the second and third elements of the array. Each of them has two children. They are elements from 4 to 7, inserted from left to right on level 3.
Similarly, we fill up level 4 and so on until we are out of the array element. The total number of levels is called the tree's height, which is 4 in our case. Each element of the binary tree is called a node. The nodes that don't have any children, like elements from index 6 to 10 in our example, are called the leaves (singular. leaf).

Building a max-heap from an array

As we want to sort the array in ascending order, we have to build a max-heap first. On the other hand, we would be required to construct a min-heap to sort the array in descending order.

The rule of thumb for building a max-heap is: the parent element will always be larger than its children. We start from the middle segment. Here the length of the array is 10. So we will begin from the 5th element. If we had 11 elements in our array, we also would have started from the 5th element. Here the rule is: divide array length by two and take the greatest integer less than the result. We usually call it the floor value, and the ⌊ ⌋ symbol denotes it.

The following image illustrates the process of building a max-heap from the array:

Our 5th element is 12. It has one child: 13. To satisfy the max-heap property, the parent must be greater than the children; we exchange 12 and 13 (Figure 1).

Next, we take our 4th element, which is 11. It has two children: 1 and 5. They obey max-heap property. So we move to the 3rd element, which is 3. It has two children: 8 and 17. Both are larger than 3. In such a case, we exchange 3 with the largest child, who is 17 (Figure 2).

Now let's move our attention to 2nd element: 6. Its children are 11 and 13. We exchange 6 with 13 as it is the largest child (Figure 3). But after the exchange, 12 becomes the child of 6, and it doesn't follow the max-heap rule. So, we again exchange 6 and 12 (Figure 4).

Last, we take the first element, 4. We exchange it with the largest child, 17. And again, exchange 4 with 8 to maintain heap property. Finally, we obtain our complete binary max-heap.

Now, let us summarize the process of building a max-heap from the array: We start from the ⌊(array length)/2⌋ element to the first element. For each component, we recursively move the element down to the tree, maintaining the max-heap property. Here the heart of the process is the recursive process of moving an element down to the tree, holding the max-heap property, and we call this process "Heapify." By using the heapify process for each element from ⌊(array length)/2⌋ element to the first element, we obtain a max-heap.

When we use extract_max, it calls heapify to return the correct order of the elements. However, we don't need to change the order of the last elements, since they are already sorted. To do this, we will change heapify by adding a parameter responsible for an additional border of possible changes.

Pseudocode for heapify

function heapify(T, index_now, last_index):                                                              // a new argument (last_index) has been added, above which the loop does not work
    while index_now <= len(T) and index_now <= last_index:                                     // interrupting the loop when we reach the last_index 
        index_left = index_now * 2
        index_right = index_now * 2 + 1
        largest = index_now

        if index_left <= len(T) and index_left <= last_index and T[index_left] > T[largest] then:    //also, nothing needs to be changed if the child elements have crossed the border last_index
            largest = index_left

        if index_right <= len(T) and index_right <= last_index and T[index_right] > T[largest]then: //also, nothing needs to be changed if the child elements have crossed the border last_index
            largest = index_right

        if largest == index_now then:
            break
        else:
            T[largest], T[index_now] = T[index_now], T[largest]
            index_now = largest

Pseudocode for building max-heap

function build_max_heap(A):        // takes an array as a parameter
    for i in [floor(len(A)/2), 1]: // cycle from the middle of the array (rounding down) to the beginning
        heapify(A, i, len(A))      // calling heapify for the current element (without restrictions)

Now we don't want extract_max to return the root element, but we need to swap it with the last unsorted element, and then sort the rest of the heap using the updated heapify.

Pseudocode for extract max

function extract_max(T, last_index):              // accepts an array and a constraint for heapify
    T[1] = T[last_index+1]                        // swapping the root and the element
    T[last_index+1] = T[1]                        // outside of the heapify operation
    heapify(T, 1, last_index)                     // calling heapify for the root with the last_index constraint

Heapsort

Here are the array and binary heap representations of the max-heap we have just built:

As this array now represents a max-heap, we know for sure that the first element of the array is the largest. At this point, we interchange the first element 17 and the last element 6 of the array. Now we no longer consider the last element 17 as a part of the heap (Figure 1 below).

So, our array has two features: index 1 to 9 representing a binary tree, and index 10 is just an element of A but not a part of the heap which is colored in blue in the illustration. We will call the length of the portion representing heap A.heap-length, and we will call the whole array length A.length. A.heap-length will always be less than or equal to A.length.

The heap in figure 1 has lost its max-heap property. So we have to heapify the root element 6. We will exchange 6 with the most significant element, 13. Next, we will exchange 6 with 12 to preserve max-heap property. Now, look at the max-heap and the array A in figure 2.

Again, we have got the next largest number, 13, at the root. Same as before, exchange it with the last heap element 5 and exclude 13 from the heap. This is shown in figure 3. So, our heap length reduces to 8. Once more, heapify the structure again (figure 4). Now exchange the root element 12 and the last element 1, and exclude 12 from the tree. Next, max-heapify the structure, extract the root element, and put it outside of the tree.

We have to perform those operations recursively until we remove all elements from the tree. Finally, we will obtain a sorted array A in ascending order:

Pseudocode for heapsort

function heapsort(A):             // takes an array as a parameter
    build_max_heap(A)             // converting an array to max-heap
    for i in [1, len(A)-1]:       // cycle n-1 times (because the last element will already be in its place)
        extract_max(A, len(A)-i)  // calling extract_max with restriction

Complexity

• Heapify — From the pseudocode of the heapify algorithm, it is clear that its performance depends on the height of the heap. If height increases, the number of operations increases. And we know that the height of a binary tree with n elements is $log(n)$.

• Building max-heap — This process requires calling the heapify function for almost half of the input elements and, for each element, we require $log(n)$ time complexity at most. So clearly, its time complexity must be greater than the heapify process. The time complexity of building max-heap is $O(n)$.

• Heapsort — First, building the max-heap demands time $O(n)$. Then we call heapify procedure $(n-1)$ times and each requires $O(log(n))$ time. Altogether the heapsort process needs $O(n log(n))$ time.

Let's think about a best-case and a worst-case scenario of the heapsort algorithm. First, think about the case where you have input an array sorted in descending order. In this case, if you represent the data in a binary heap, then it is already a max-heap. You can easily skip building Max-heap steps and directly start sorting, and indeed, it would require less time. On the other hand, if you input an ascendingly sorted list, you have to heapify each element starting from the middle to build max-heap. So, this would require more comparisons and would take more time.

Conclusion

In summary, the steps of the heapsort algorithms are:

1. Build a max-heap from your input data.

2. Exchange the root and last element.

3. Exclude the last element from the binary heap and store it outside of the binary tree.

4. Heapify the root element.

5. Repeat from step 2 until your tree size reduces to 2.

Every algorithm has some advantages and disadvantages, and the heapsort is no exception. But it is considered one of the best sorting algorithms for a reason. The most important thing about the heapsort is that it is an in-place algorithm, i.e. no additional space is required to perform heapsort. For this reason, if there is a shortage in memory, we must consider heapsort to sort. The next important thing about the heapsort is its performance. Although its time complexity is $O(nlog(n))$, practically, it requires less time than that. Besides, its performance remains the same for a large amount of data. Apart from these pros and cons, the best thing it can do is extract the largest or smallest number from an array. This feature has a significant application: priority queues. Operating systems use it to manage their tasks and processes.