Chapters

Hide chapters

Data Structures & Algorithms in Dart

First Edition · Flutter · Dart 2.15 · VS Code 1.63

Section VI: Challenge Solutions

Section 6: 20 chapters
Show chapters Hide chapters

18. Heapsort
Written by Vincent Ngo & Jonathan Sande

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled 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 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 heap 4 1 5 8 10 Min heap 4 8 5 2 1

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.

8 5 2 19 21 32 35 1 4

9 6 7 62 2 7 29 37 10

98 5 33 6 41 25 4 1 0

Sorting the List

Once you have a heap, you can go on to use its properties to sort the list in ascending order.

4 68 0 24 47 9 7 58 8

3 24 6 90 23 5 8 9 67

67 5 73 2 88 9 7 45 8

59 4 4 4 77 04 9 3 35

2 5 96 9 4 2 43 57 17 8 2 0 81 6 6 83 48 72

7 9 0 5 2 45 54 75 03 31 6 4 8 7 6 24 93 94

5 9 0 1 77 39 14 93 3 7 22 1 0 9 6 20 50 85

5 4 2 53 98 24 79 9 9 3 2 21 3 6 6 30 91 64

0 3 63 07 08 91 2 8 1 4 5 8 33 6 8 82 65 72

9 55 95 52 90 9 8 5 5 0 1 6 0 88 3 35 75 43

6 0 5 6 0 59 54 36 85

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.

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;
}
import 'package:starter/heapsort.dart';

void main() {
  final sorted = heapsort([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<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;
}

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 = [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.
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.
© 2024 Kodeco Inc.

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a Kodeco Personal Plan.

Unlock now