18 Chapter 18 Solutions

Solution to Challenge 1

Heapsort requires two steps:

1. Converting a list to a heap.
2. Repeatedly moving the root of the heap to an ordered list.

Step one is where you’ll find the difference in the number of comparisons needed.

5, 4, 3, 2, 1

[5, 4, 3, 2, 1] will yield the fewest number of comparisons since it’s already a max-heap and no swaps take place.

When building a max-heap, you only look at the parent nodes because these are the nodes that might need to sift down. In this case, there are two parent nodes, each with two comparisons. You compare 4 with 2 and 1. Then you compare 5 with 4 and 3. Since none of these comparisons require a swap, no further comparisons are necessary.

2143542135

1, 2, 3, 4, 5

[1, 2, 3, 4, 5] will yield the most number of comparisons. You first compare 2 with 4 and 4 with 5. Since 2 is smaller, you swap it with 5. Then you compare 1 with 5 and 5 with 3. Since 1 is smaller, you sift it down, swapping it with the 5. The down-sift now requires comparing 1 with 4 and 4 with 2, which will lead to swapping 1 with 4.

452315423514231

The sorting itself will take additional comparisons, but these are equivalent since both lists have already been converted to heaps.

Solution to Challenge 2

There are multiple ways to sort in descending order.

Using reversed

The easiest solution is to simply use the reversed method on List:

final list = [6, 12, 2, 26, 8, 18, 21, 9, 5];
final ascending = heapsort(list);
final descending = ascending.reversed;

This gives you an iterable, but you can convert it to a list with toList if needed.

Reimplementing Heapsort

If you’re using the heapsort function that you implemented earlier in the chapter, then replace Priority.min with Priority.max.

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

This will fill the list by pulling the max values off of the heap, resulting in a list of descending values.

Reimplementing heapsortInPlace

It’s also easy to reimplement your heapsortInPlace extension to sort in ascending order. Again, all you have to do is change the heap priority.

Go to _siftDown and look for the two comparisons:

this[left].compareTo(this[chosen]) > 0
// and
this[right].compareTo(this[chosen]) > 0

Then switch > 0 to < 0:

this[left].compareTo(this[chosen]) < 0
// and
this[right].compareTo(this[chosen]) < 0

This will create an internal min-heap so that during the sorting step the lowest values will be pulled off the heap and placed at the end of the list.