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, “The Heap Data Structure.”

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 so that they 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. As a result of this swap, the last element of the array is in the correct spot, but the heap is now invalidated. The next step is, thus, to sift down the new root note 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.

Starting to see a pattern? Heap sort 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 simply 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 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: In order to support heap sort, you’ve added an additional parameter upTo to the siftDown method. This way, the sift down only uses the unsorted part of the array, which shrinks with every iteration of the loop.

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 should print:

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

Performance

Even though you get the benefit of in-memory sorting, the performance of heap sort is O(n log n) for its best, worse and average cases. This 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.

Heap sort 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 with respect to the original deck.

Key points

• Heap sort leverages the max-heap data structure to sort elements in an array.
• Heap sort sorts its elements by following a simple pattern:
  • Swap the first and last element.
  • Perform a sift-down from the root to satisfy the requirement of being a heap.
  • Decrease the array size by one, since the element at the end will be the largest element.
  • Repeat these steps till you reach the start of the array.