Understanding Heapsort | Baeldung on Computer Science

1. Overview

Heapsort is an elegant and robust algorithm for sorting. It’s optimal since it takes $O(n\log n)$ time to sort $n$ items, which is the best we can do with comparison-based sorting algorithms.

In this tutorial, we’ll intuitively explain Heapsort’s essential steps and the algorithm.

2. Heaps

A heap is a special kind of binary tree with the following properties:

It’s a complete binary tree
The value at each node is greater than or equal to the values of its child nodes

Here’s an example:

Given any complete binary tree, we can convert it into a heap using the procedure max-heapify in $O(n)$ time.

A complete binary tree of $n$ nodes can be represented compactly by an array $A$ of size $n$ . The children of a node at the $i$ th position are $A[2i+1]$ and $A[2i+2]$ . For example, the children of node $A[1]$ are $A[3]$ and $A[4]$ . This is how we store the above heap in an array:

3. Sorting with Heaps

To sort an array in place using heaps, we have first to convert the array to a heap.

Then, we’ll have to divide the array logically between a logical max-heap on the left and a sorted array on the right. We start the process with the heap occupying the totality of the array and the sorted array having zero elements.

Then, we swap the first element with the array with the last and decrease the size of the logical heap by one while increasing the size of the sorted array by one.

We have no guarantees that after swapping the max element of the heap, the heap invariant will be maintained; hence, we have to correct it to establish the heap property.

We’ll repeat the process until the logical heap has zero elements and the sorted array spans the total of the input array.

3.1. Using a Sub Array as a Heap

Given these requirements, we start by redefining max-heapify to have an interface that allows us to treat a sub-section of an array as a logical heap. To differentiate the function, we’ll call it swift-down:

algorithm swift_down(heap, start, end):
    // INPUT: 
    //   heap - array representing the heap, start - index to start restructuring, 
    //   end - boundary index for restructuring.
    // OUTPUT: 
    //   Modifies the heap in place to maintain the heap property from start to end.
    //
    // Invariant: 
    //   Heap property is maintained for all array elements between start and end.

    index <- start
    while index < end:
        left_child <- 2 * index + 1  // Compute the left child index
        right_child <- 2 * index + 2 // Compute the right child index 
        // If no child nodes, end the algorithm 
        if left_child >= end:
            return

        // Determine the larger child
        larger_child <- left_child
        if right_child < end and heap[left_child] < heap[right_child]:
            larger_child <- right_child

        // If current node is smaller, swap with the larger child
        if heap[index] < heap[larger_child]:
            swap(heap[index], heap[larger_child])
            index <- larger_child
        else:
            // Node is correctly placed, end the algorithm
            return

The stop argument enables us to ignore any elements to the right of it, creating the logical partition between the heap and the section of the array already sorted.

3.2. Heapifying the Array Using Sift-Down

We can also implement the Heapify function using Sift-Down to avoid confusion and code repetition:

algorithm heapify(arr):
    // INPUT: 
    //   arr - array representing the heap to be transformed.
    // OUTPUT: 
    //   Modifies the array in place to form a heap structure.
    //
    // Invariant: 
    //   After completion, the array satisfies the heap property.
    
    start <- len(heap) // 2 // Begin with the last non-leaf node while start >= 0:
        swift_down(heap, start, len(heap))  // Adjust the subtree at start to satisfy heap property
        start <- start - 1  // Move to the previous node

3.3. Placing the Maximum at the Right Position

A heap’s maximum element is the one at position 0. So, if we want to sort our array in a non-decreasing order, we must put its maximal element at the end. So, we swap $A[0]$ with $A[n]$ .

Our job isn’t done since the remaining elements $A[0] \cdots A[n-1]$ are unsorted. If we found the maximum of the subarray $A[0] \cdots A[n-1]$ and placed it at the second-to-last position, we would have the last two elements in their correct positions. So, we can repeat these steps until getting a fully sorted array.

For instance, here’s how the first step unfolds with our previous example:

However, there’s a problem! When we put 11 at position 0, we violated the heap property since 11 is not greater than its children 42 and 30. Therefore, we need to correct the heap so that the new node 0 does indeed contain the next maximum element (which is 42).

3.4. Correcting the Heap With Sift-Down

To correct the error caused by replacing the root node, we use the procedure Sift-Down. We start at the root and down to a leaf node. Our objective is to look at a node and its two children and swap the node with whichever child is greater (if any):

Sift-Down starts at the root of a subtree, indicated by start, and ends at stop. During each pass, it checks if either of the two children of the root are more significant than the root. If so, it swaps the root and the greater child and sets start to the former location of the greater child.

If neither of the two children has a value greater than their parent, the procedure proceeds with the left child.

3.5. An Example of Sift-Down

In the following diagrams, blue triangles denote node comparisons to their children.

After placing the maximal element at its position in the above example, we made node one greater than node 0. So, we interchange their values, as shown by the double-headed blue arrow:

Now, we compare node 1 to its children, nodes 3 and 4. We exchange the values in nodes 1 and 3 since node 3 is the greater child:

In the final step, we check nodes 3, 7, and 8. No swapping is required here, as 11 is already greater than 2 or 5:

We’ve now obtained a new heap of 9 elements. This heap is correct, as each node has a value greater than its two children.

Our next step is to move the $2^{\textrm{nd}}$ largest element (42) to its correct place:

That results in a sorted array of size 2 (purple) and an unsorted array of size 8. To re-heapify the remainder, we apply Sift-Down to the array $A[0]\cdots A[7]$ . Afterward, we repeat the process until we sort the entire array.

3.6. Completing the Sorting Process

We’ll illustrate the remaining process using arrays. Green squares denote the heap, which shrinks in size from $n$ to 0, while purple squares indicate the sorted array, which increases in size to $n$ . The arrows indicate the transfer of the max element to its proper location. We’ve omitted other entries for clarity:

3.6. Heapsort – the Complete Pseudocode

Here’s the complete pseudocode of Heapsort:

algorithm heapsort(arr):
    // INPUT: 
    //     arr - array to be sorted.
    // OUTPUT: 
    //     Sorts the array in ascending order in place.
    //
    // Invariant: 
    //     After completion, the array will be sorted in ascending order.
    
    heapify(heap)  // Transform the array into a max heap
    end <- len(heap) - 1 while end > 0:
        // Swap the max element with the last element in the unsorted portion
        swap(heap[end], heap[0])
        end <- end - 1  // Reduce the size of the unsorted portion by one
        swift_down(heap, 0, end)  // Restore the heap property

We’ll start by transforming the array into a max heap. Then, iteratively swap the first element (max element) with the last element in the heap, reduce its size by one and restore the heap property on the new smaller heap.

As the heap decreases at the start of the array, the sorted area of the array increases at its end. Our code stops when the heap reaches size zero.

4. Complexity of Heapsort

We start our Heapsort by creating a heap using max-heapify with complexity $O(n)$ .

After this, we run Sift-Down $n$ times. This procedure moves from the tree’s root to a leaf node and takes at most $O(\log n)$ steps since we deal with complete binary trees, which have at most $\log n$ levels. So, the total time for the sifts is $O(n\log n)$ .

The time for max-heapify, $O(n)$ , is masked by the time for the sifts. Therefore, the complexity of Heapsort is $\boldsymbol{O(n\log n)}$ .

5. Heapsort vs. Selection Sort

It’s interesting to compare Heapsort with Selection Sort. Both pick and move the maximum element to its proper place at each step.

However, Selection Sort makes $n-i$ comparisons in the $i$ th iteration, which results in $O(n^2)$ complexity. In the worst case, Heapsort makes $O(\log n)$ comparisons and swaps per iteration, which is why its complexity is $O(n \log n)$ .

Heapsort uses the clever heap approach to find and place the maximal element, which is why we can consider Heapsort a refinement of Selection Sort.

6. Implementing Heapsort in Python

Python is known for its clarity and similarity to pseudocode, making it an ideal language for learning algorithms.

This section will examine a trivial heap sort implementation using Python’s built-in heap data structure. Then, we’ll translate the Heapsort pseudocode into Python code, minimizing the use of Python specifically to keep our translation as straightforward as possible. Finally, we will extend our implementation to enable our function to use sorting types beyond simple numbers.

6.1. Using Python’s Built-in Heap for Heapsort

Python includes the heapq module, which implements a min heap, which we can use to implement a trivial heapsort function. We convert the input to a min-heap using the heapify function from this module and then create a new list, using a list comprehension, by continuously removing the minimum from the heap:

import heapq

def heapsort_simple(arr):
    # Convert the list into a heap
    heapq.heapify(arr)
    # Create a new sorted list 
    # by continuously reading the min from the heap
    return [heapq.heappop(arr) for _ in range(len(arr))]

# Use example 
arr = [53, 42, 30, 17, 13, 24, 9, 2, 5, 11]
sorted_arr = heapsort_simple(arr)
print("Sorted array is:", sorted_arr)

This contrasts with our discussion so far, which used a max heap to continuously find the biggest element and move it to the end of the array. The advantage is that the min heap naturally sorts the elements in the ascending order we want in our sort function.

Many languages have adopted comprehensions, but Python’s implementation closely resembles mathematical syntax. As with other subjects in this popular language, there are many tutorials for those interested, from quick reviews to in-depth discussions.

This simple implementation has the same theoretical time and space complexity as our algorithm. Still, in the real world, we’ll pay twice the memory usage and increased execution time, as it requires creating an additional list to hold the sorted elements while still altering the input.

6.2. Implementing the Algorithm From Scratch

First, we’ll implement the sift_down function, which is the basic building block of our algorithm. Its task is to ensure a specific subsection of the array maintains the heap property and changing the positions of elements when it doesn’t:

def swift_down(heap, start, end):
    index = start
    while index = end:
            break

        # Find the larger of the two children
        larger_child = left_child
        if right_child < end and heap[left_child] < heap[right_child]:
            larger_child = right_child

        # Are we larger than our children? If so, swap with the larger child.
        if heap[index] < heap[larger_child]:
            heap[larger_child], heap[index] = heap[index], heap[larger_child]

            # Continue swift down by verifying/fixing the heap for the swapped child
            index = larger_child
        else:
            # We're larger than both children, so we're done
            break

This is a one-to-one implementation of our pseudocode function. Except we use break instead of return because it is more idiomatic to leave a loop with it.

Next, we have to translate the heapify function:

def heapify(arr):
    start = len(arr) // 2  # Start with the last non-leaf node
    while start >= 0:
        swift_down(arr, start, len(heap))
        start = start - 1

Finally, we implement the heap sort by converting the array to a max heap using sift_down, swapping the max element to the end of the array, and recreating the heap but treating the array as if it were one element smaller.

def heapsort(arr):
    # convert the arr to a max-heap in-place
    heapify(arr)
    # The initial logical heap spans the whole array  
    end = len(arr) - 1

    while end > 0:
        # Swap the max element with the last item in the logical heap
        arr[end], arr[0] = arr[0], arr[end]  
        # Shrink the heap by one element, the previous max element is now in 
        # the right position of an ascendently sorted array 
        end = end - 1
        # Restore the max-heap propery in the new logical heap
        swift_down(arr, 0, end)

6.3. Add Support for Multiple Types

So far, we have concerned ourselves with sorting numeric data only. Still, in real applications, we’ll have to deal with different kinds of data, even some that might not support the less-than and similar operators.

Python, like Scala, supports higher-order functions, and we can use them to make our implementation more flexible and add type hints to make it more robust if we use a type checker like mypy:

from typing import List, Callable

def swift_down(heap: List[int], start: int, end: int, compare: Callable[[int, int], bool]) -> None:
    index = start
    while index = end:
            break

        larger_child = left_child
        if right_child  None:
    start = len(arr) // 2
    while start >= 0:
        swift_down(arr, start, len(arr), compare)
        start -= 1

def heapsort(arr: List[int], compare: Callable[[int, int], bool] = lambda x, y: x  None:
    heapify(arr, compare)
    end = len(arr) - 1
    while end > 0:
        arr[end], arr[0] = arr[0], arr[end]
        end -= 1
        swift_down(arr, 0, end, compare)


# Example usage for integers
arr_int = [53, 42, 30, 17, 13, 24, 9, 2, 5, 11]
heapsort(arr_int, compare=lambda x, y: x  y)
print("Sorted array of integers:", arr_int)


# Example usage for strings based on their length
arr_str = ["banana", "apple", "pear", "grape"]
heapsort(arr_str, compare=lambda x, y: len(x) < len(y))
print("Sorted array of strings by length:", arr_str)

As a bonus, we can use the same code to sort arrays in ascending or descending order or choose the rules for sorting, like sorting strings by their length instead of lexicographic order.

7. Conclusion

In this article, we explained the Heapsort algorithm for sorting an array in non-descending order. It uses the fact that a Max-Heap’s maximum element is at its root.

It’s simple to modify this algorithm to use a Min-Heap, leading to sorting in non-ascending order. The complexity of Heapsort is $O(n\log n)$ , which is the best possible for sorting algorithms that use comparisons.

Core Concepts

Operating Systems

Artificial Intelligence

Graph Theory

Latex

Full Archive

About Baeldung