18 Heapsort

Heapsort is a comparison-based algorithm that sorts a list in ascending order using a heap. This chapter builds on the heap concepts presented in Chapter 13, “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 or equal to their children.
2. In a min-heap, all parent nodes are smaller than or equal to their children.

The diagram below shows a max- and min-heap with parent node values highlighted:

Max heap415810Min heap48521

Once you have a heap, the sorting algorithm works by repeatedly removing the highest priority value from the top of the heap.

Example

A concrete example of how heapsort works will help to make things more clear.

Building a Heap

The first step in a heapsort algorithm is to create a heap from an unsorted list.

Here’s the unsorted list that this example will begin with:

6822112182695

To sort from lowest to highest, the heapsort algorithm that this example will use needs a max-heap. This conversion is done by sifting all the parent nodes down so they end up in the right spot. If you need a review of how creating a heap works, look back at Chapter 13, “Heaps”. The resulting max-heap is shown below:

6591282211826

This corresponds with the following list:

2682121218965

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

Sorting the List

Once you have a heap, you can go on to use its properties to sort the list 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 list is in the correct spot but invalidates the heap.

8212121896265

Thus, the next step is to sift the new root node 5 down until it lands in its correct position. You need to exclude the last element of the list from your heap since you no longer consider it part of the heap but of the sorted list. As a result of sifting 5 down, the second largest element 21 becomes the new root.

8182122159626

You can now repeat the previous steps. Swap 21 with the last element 6, and move the end of the heap up by one:

2181821259266

Then sift 6 down, and 18 will rise to the top:

2186212185926

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

After swapping 18 and 2, move the end of the heap up. Then sift the 2 down:

86122592621188691252261821

Swap the 12 and 5. Move the end of the heap up. Sift the 5 down:

86952262118121256892261821

Swap the 9 and 5. Move the end of the heap up. Sift the 5 down:

68522621181299126582261821

Swap the 8 and 2. Move the end of the heap up. Sift the 2 down:

65226211812988912256261821

Swap the 6 and 2. Move the end of the heap up. Sift the 2 down:

52262118129866891225261821

Swap the 5 and 2. Move the end of the heap up. No need to sift the 2:

22621181298655689122261821

Move the end of the heap up and you’re finished:

5268912261821

This sorting process is very similar to selection sort from Chapter 15, “O(n²) Sorting Algorithms”.

Implementation

You’re going to implement two versions of heapsort. The first one will use the Heap class you created in Chapter 13, “Heaps”. It’s quite easy to implement. However, it won’t follow the exact algorithm described in the example above. For your second implementation, though, you will follow this algorithm. Although the second implementation will take a little more work, space efficiency will be better.

Using Your Heap Class

Open the starter project for this chapter. In lib/heap.dart, you’ll find the Heap class that you created in Chapter 13.

Now create a new file in lib called heapsort.dart. Then add the following code:

import 'heap.dart';

List<E> heapsort<E extends Comparable<dynamic>>(List<E> list) {
  // 1
  final heap = Heap<E>(
    elements: list.toList(),
    priority: Priority.min,
  );
  // 2
  final sorted = <E>[];
  // 3
  while (!heap.isEmpty) {
    final value = heap.remove();
    sorted.add(value!);
  }
  return sorted;
}

That’s it for the entire implementation of heapsort! Nice, huh? The simplicity is because the heavy lifting is done by the Heap class. Here’s what’s going on:

1. You first add a copy of the input list to a heap. Heap sorts this into a min-heap.
2. Create an empty list to add the sorted values to.
3. Keep removing the minimum value from the heap until it’s empty. Since you’re adding to the end of the list, sorted will be sorted.

Time to test it out. Open bin/starter.dart and replace the contents of the file with the following code:

import 'package:starter/heapsort.dart';

void main() {
  final sorted = heapsort([6, 12, 2, 26, 8, 18, 21, 9, 5]);
  print(sorted);
}

Run the code and it should print the ordered list you see below:

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

Although you have a properly sorted list, this algorithm didn’t behave like the description in the example section. The diagrams there showed an in-place sort within a single list. However, the heapsort function you made just now used two additional lists, one inside the heap and another to store the sorted results. It also used a min-heap rather than a max-heap.

Sorting in Place

In this section, you’ll rewrite heapsort without using the Heap class. The sort will take an input list and mutate that list in place in the manner described in the example section.

Creating an Extension

Since you want to mutate the list itself, you can create an extension method on List. Add the following code at the bottom of lib/heapsort.dart:

extension Heapsort<E extends Comparable<dynamic>> on List<E> {

  // more to come
}

Preparing Private Helper Methods

Before implementing the main sort method, you need to add a few other helper methods. They’re just a copy-and-paste of what you wrote earlier when you made the Heap class. Add the following methods to the Heapsort extension body:

int _leftChildIndex(int parentIndex) {
  return 2 * parentIndex + 1;
}

int _rightChildIndex(int parentIndex) {
  return 2 * parentIndex + 2;
}

void _swapValues(int indexA, int indexB) {
  final temp = this[indexA];
  this[indexA] = this[indexB];
  this[indexB] = temp;
}

These will allow you to find the heap node’s left or right child index and also swap values between nodes. If you’re unfamiliar with how any of these work, go back and review Chapter 13, “Heaps”.

Modifying the Sift Method

You also need a method to help you sift the root index down. This one is a little different than the one in Heap. Add the following code to Heapsortextension:

// 1
void _siftDown({required int start, required int end}) {
  var parent = start;
  while (true) {
    final left = _leftChildIndex(parent);
    final right = _rightChildIndex(parent);
    var chosen = parent;
    // 2
    if (left < end && 
        this[left].compareTo(this[chosen]) > 0) {
      chosen = left;
    }
    // 3
    if (right < end && 
        this[right].compareTo(this[chosen]) > 0) {
      chosen = right;
    }
    if (chosen == parent) return;
    _swapValues(parent, chosen);
    parent = chosen;
  }
}

Like before, _siftDown swaps a parent value with its left or right child if one of them is larger, and continues to do so until the parent finds its correct place in the heap. However, this time there are a few minor differences:

1. start is the index of the node that you want to sift down within the heap. end marks the end of the heap. This will allow you to resize your heap while maintaining the size of the list.
2. Check if the left child is within the bounds of the heap and is larger than the parent. This implementation assumes a max-heap.
3. Do the same for the right child.

Adding the Main Extension Method

Now you’re finally ready to perform the actual in-place heapsort. Add the following method to the Heapsort extension:

void heapsortInPlace() {
  if (isEmpty) return;
  // 1
  final start = length ~/ 2 - 1;
  for (var i = start; i >= 0; i--) {
    _siftDown(start: i, end: length);
  }
  // 2
  for (var end = length - 1; end > 0; end--) {
    _swapValues(0, end);
    _siftDown(start: 0, end: end);
  }
}

These are the two main tasks of heapsort:

1. Turn the list into a max-heap. Some people call this task heapify.
2. Sort the list in ascending order. You do that by swapping the max value, which is at the front of the list, with a smaller value at the end of the heap. Sift that smaller value down to its proper location and then repeat, each time moving the heap’s end index up by one to preserve the sorted values at the end of the list.

Testing it Out

To check that your in-place heapsort works, head back to bin/starter.dart and replace the contents of main with the following code:

final list = [6, 12, 2, 26, 8, 18, 21, 9, 5];
print(list);
list.heapsortInPlace();
print(list);

Run that and you should see the following output:

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

It works!

Performance

The performance of heapsort 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 down-sift, which is an O(log n) operation.

The space complexity of your first implementation, heapsort, was linear since you needed the extra list copies. However, your second implementation, heapsortInPlace, had a constant O(1) space complexity.

Heapsort isn’t a stable sort because it depends on how the elements are put into the heap. If you were heapsorting a deck of cards by their rank, for example, you might see their suite change order compared to the original deck.

Challenges

Here are a couple of small challenges to test your knowledge of heapsort. You can find the answers in the Challenge Solutions section as well as in the supplementary materials that accompany the book.

Challenge 1: Theory

When performing heapsort in ascending order, which of these starting lists requires the fewest comparisons?

• [1, 2, 3, 4, 5]
• [5, 4, 3, 2, 1]

You can assume that the implementation uses a max-heap.

Challenge 2: Descending Order

The current implementations of heapsort in this chapter sort the elements in ascending order. How would you sort in descending order?

Key Points

• Heapsort leverages the heap data structure to sort elements in a list.
• The algorithm works by moving the values from the top of the heap to an ordered list. This can be performed in place if you use an index to separate the end of the heap from the sorted list elements.