19.
Chapter 19 Solutions
Written by Jonathan Sande
Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as text.
Solution to Challenge 1
Heapsort requires two steps:
- Converting a list to a heap.
- 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.
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.
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 = <num>[6, 12, 2, 26, 8, 18, 21, 9, 5];
final ascending = heapsort(list);
final descending = ascending.reversed;
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<E>>(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;
}
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.
this[left].compareTo(this[chosen]) > 0
// and
this[right].compareTo(this[chosen]) > 0
this[left].compareTo(this[chosen]) < 0
// and
this[right].compareTo(this[chosen]) < 0