Heapsort

Heapsort is an algorithm that sorts arrays by inserting the data into a heap data structure and then repeatedly extracting the root of the heap. Heapsort is a particularly time-efficient algorithm due to its O(n log n) time complexity in every case.

In this article, we’ll go over the necessary steps to implement a heapsort algorithm.

How the algorithm works

Here’s how we’ll accomplish the implementation of heapsort:

1. Build a max-heap to store the data from an unsorted list.
2. Extract the largest value from the heap and place it into a sorted list.
3. Replace the root of the heap with the last element in the list. Then, rebalance the heap.
4. Once the max-heap is empty, return the sorted list.

Let’s break these steps down a little more.

Build a max-heap

For this algorithm, we’ll want to build out a max-heap. As a reminder, in a max-heap, the root value is the largest value. Each parent node must have a larger value than its associated children.

Imagine we had the following list of unsorted values:

[14, 11, 2, 20, 3, 10, 3]

By placing our values into a max-heap data structure, our list would look like this:

[20, 11, 14, 2, 10, 5, 3]

We can visualize the above max-heap like so:

Extract the root of the heap

In order to sort our data, we’ll repeatedly extract and remove the largest value from the heap until it’s empty. By following the rule of heaps, we can expect to find the largest value located at the root of the heap.

After removing the largest value, we can’t just leave our heap without a root because that would cause us to have two orphaned nodes. Instead, we can swap our root node with the last element in the heap. Since the last element has no children, we can easily remove the value from the heap.

This step does cause one major problem. By swapping the two elements, our root node isn’t the largest value in the heap! We’ll need to restructure the heap in order to ensure that it’s balanced.

Restore the heap: heapify down

With the root value no longer holding the largest value, we’ve violated an important rule about heaps: the parent must contain a value that is larger than its children’s values.

We can fix this though! In the previous lesson, we learned how to heapify up: adding a value to the end of a heap and working our way up the data structure to find its correct placement. Now we need to heapify down. To heapify down, we’ll first compare our new root value to its children. Then, we’ll select the child with the larger value and swap it with the root value. We’ll continue working our way down the heap until it is balanced again:

In the example above, we swap the original root value 20 with the right-most child 3. With 3 as the new root, we compare the value to its child value, 14. Since 14 is greater than 3, we will swap the two values and make 14 the new root. Next, we’ll compare 3 to its new child value, 5. Once again, the child value is greater than its parent, so we will swap 3 and 5. With no more children to compare 3 to, our heap has been rebalanced.

Repeat

We’ll repeat the process of swapping the root and the last element, extracting the largest value, and rebalancing the heap while the data structure has a size greater than 1. Once we hit this condition, we will have an ordered list of values.

Review

Great job completing this article! We learned that a heapsort is a sorting algorithm that uses heaps to organize data. To implement heapsort, we did the following:

1. We placed an unordered list into a max-heap.
2. While the max-heap had at least 1 element, we extracted the root of the heap and swapped it with the left-most child node. The extracted value was then placed at the beginning of a list that contains the sorted values.
3. After the left-most child was placed at the root of the heap, we rebalanced the heap by comparing the new root value with the next largest child; if the child was greater than the parent, we swapped the two values. We continued this process until the heap was restored.
4. Once the heap was empty, we returned the sorted list.