32. Heapsort

Written by Vincent Ngo

Heapsort is another comparison-based algorithm that sorts an array in ascending order using a heap. This chapter builds on the heap concepts presented in Chapter 22, “Heaps”.

Heapsort takes advantage of a heap being, by definition, a partially sorted binary tree with the following qualities:

1. In a max heap, all parent nodes are larger than their children.
2. In a min heap, all parent nodes are smaller than their children.

The diagram below shows a heap with parent node values underlined:

Getting started

Open up the starter playground. This playground already contains an implementation of a max heap. Your goal is to extend Heap so it can also sort. Before you get started, let’s look at a visual example of how heap sort works.

Example

For any given unsorted array, to sort from lowest to highest, heap sort must first convert this array into a max heap:

This conversion is done by sifting down all the parent nodes to end up in the right spot. The resulting max heap is:

This corresponds with the following array:

Because the time complexity of a single sift-down operation is O(log n), the total time complexity of building a heap is O(n log n).

Let’s look at how to sort this array in ascending order.

Because the largest element in a max heap is always at the root, you start by swapping the first element at index 0 with the last element at index n - 1. After the swap, the last element of the array is in the correct spot but invalidates the heap. The next step is, thus, to sift down the new root node 5 until it lands in its correct position.

Note that you exclude the last element of the heap as you no longer consider it part of the heap but of the sorted array.

As a result of sifting down 5, the second largest element 21 becomes the new root. You can now repeat the previous steps, swapping 21 with the last element 6, shrinking the heap and sifting down 6.

Are you starting to see a pattern? Heapsort is very straightforward. As you swap the first and last elements, the larger elements make their way to the back of the array in the correct order. You repeat the swapping and sifting steps until you reach a heap of size 1.

The array is then fully sorted.

Note: This sorting process is very similar to selection sort from Chapter 26.

Implementation

Next, you’ll implement this sorting algorithm. The actual implementation is very simple, as the heavy lifting is already done by the siftDown method:

extension Heap {
  func sorted() -> [Element] {
    var heap = Heap(sort: sort, elements: elements) // 1
    for index in heap.elements.indices.reversed() { // 2
      heap.elements.swapAt(0, index) // 3
      heap.siftDown(from: 0, upTo: index) // 4
    }
    return heap.elements
  }
}

Here’s what’s going on:

1. You first make a copy of the heap. After heap sort sorts the elements array, it is no longer a valid heap. By working on a copy of the heap, you ensure the heap remains valid.
2. You loop through the array, starting from the last element.
3. You swap the first element and the last element. This swap moves the largest unsorted element to its correct spot.
4. Because the heap is now invalid, you must sift down the new root node. As a result, the next largest element will become the new root.

Note: To support heap sort, you’ve added the upTo parameter to the siftDown method. This way, the sift down only uses the unsorted part of the array, which shrinks with every loop iteration.

Finally, give your new method a try:

let heap = Heap(sort: >, elements: [6, 12, 2, 26, 8, 18, 21, 9, 5])
print(heap.sorted())

This code should print:

[2, 5, 6, 8, 9, 12, 18, 21, 26]

Performance

Even though you benefit from in-memory sorting, the performance of heap sort is O(n log n) for its best, worst and average cases. This uniformity in performance is because you have to traverse the whole list once and, every time you swap elements, you must perform a sift down, which is an O(log n) operation.

Heapsort is also not a stable sort because it depends on how the elements are laid out and put into the heap. If you were heap sorting a deck of cards by their rank, for example, you might see their suite change order compared to the original deck.

Key points

• Heapsort leverages the max heap data structure to sort elements in an array.
• Heapsort sorts its elements by following a simple pattern:

1. Swap the first and last element.
2. Perform a sift-down from the root to satisfy the requirement of being a heap.
3. Decrease the array size by one since the element at the end will be the largest element.
4. Repeat these steps till you reach the start of the array.