19.
Heapsort
Written by Jonathan Sande
Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as text.
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 14, “Heaps”.
Heapsort takes advantage of a heap being, by definition, a partially sorted binary tree with the following qualities:
- In a max-heap, all parent nodes are larger than or equal to their children.
- 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:
Once you have a heap, the sorting algorithm repeatedly removes 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.
Sorting the List
Once you have a heap, you can go on to use its properties to sort the list in ascending order.
Implementation
You’re going to implement two versions of heapsort. The first one will use the Heap class you created in Chapter 14, “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 improve.
Using Your Heap Class
Open the starter project for this chapter. In lib/heap.dart, you’ll find the Heap class you created in Chapter 14.
import 'heap.dart';
List<E> heapsort<E extends Comparable<E>>(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;
}
import 'package:starter/heapsort.dart';
void main() {
final sorted = heapsort<num>([6, 12, 2, 26, 8, 18, 21, 9, 5]);
print(sorted);
}
[2, 5, 6, 8, 9, 12, 18, 21, 26]
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<E>> 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.
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;
}
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 Heapsort extension:
// 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;
}
}
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);
}
}
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 = <num>[6, 12, 2, 26, 8, 18, 21, 9, 5];
print(list);
list.heapsortInPlace();
print(list);
[6, 12, 2, 26, 8, 18, 21, 9, 5]
[2, 5, 6, 8, 9, 12, 18, 21, 26]
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.
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?
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.