17.
Heap Sort
Written by Matei Suica, Kelvin Lau and Vincent Ngo
Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as text.
Heapsort is another comparison-based algorithm that sorts an array in ascending order using a heap. This chapter builds on the heap concepts presented in Chapter 12, “Heap Data Structure.”
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 their children.
- In a min heap, all parent nodes are smaller than their children.
The diagram below shows a heap with parent node values underlined:
Getting started
Open up the starter project. This project already contains an implementation of a heap. Your goal is to extend Heap so it can also sort. Before you get started, let’s look at a visual example of how heap sort works.
Example
For any given unsorted array, to sort from lowest to highest, heap sort must first convert this array into a heap:
Implementation
Next, you’ll implement this sorting algorithm. The actual implementation is simple. You’ll be performing the sort on an Array and reusing the algorithms already implemented in Heap in the form of extension functions. You’ll reorder the elements using heapify(). After that, the heavy lifting will be done by a siftDown() method.
private fun leftChildIndex(index: Int) = (2 * index) + 1
private fun rightChildIndex(index: Int) = (2 * index) + 2
fun <T> Array<T>.siftDown(
index: Int,
upTo: Int,
comparator: Comparator<T>
) {
var parent = index
while (true) {
val left = leftChildIndex(parent)
val right = rightChildIndex(parent)
var candidate = parent
if (left < upTo &&
comparator.compare(this[left], this[candidate]) > 0
) {
candidate = left
}
if (right < upTo &&
comparator.compare(this[right], this[candidate]) > 0
) {
candidate = right
}
if (candidate == parent) {
return
}
this.swapAt(parent, candidate)
parent = candidate
}
}
fun <T> Array<T>.heapify(comparator: Comparator<T>) {
if (this.isNotEmpty()) {
(this.size / 2 downTo 0).forEach {
this.siftDown(it, this.size, comparator)
}
}
}
fun <T> Array<T>.heapSort(comparator: Comparator<T>) {
this.heapify(comparator)
for (index in this.indices.reversed()) { // 1
this.swapAt(0, index) // 2
siftDown(0, index, comparator) // 3
}
}
"Heap sort" example {
val array = arrayOf(6, 12, 2, 26, 8, 18, 21, 9, 5)
array.heapSort(ascending)
print(array.joinToString())
}
---Example of Heap sort---
2, 5, 6, 8, 9, 12, 18, 21, 26
Performance
Even though you get the benefit of in-memory sorting, the performance of heap sort is O(n log n) for its best, worse and average cases. This is because you have to traverse the whole array once and, every time you swap elements, you must perform a sift down, which is an O(log n) operation.
Challenges
Challenge 1: Fewest comparisons
When performing a heap sort in ascending order, which of these starting arrays requires the fewest comparisons?
Solution 1
When sorting elements in ascending order using heap sort, you first need a max heap. What you really need to look at is the number of comparisons that happen when constructing the max heap.
Challenge 2: Descending sort
The current example of heap sort sorts the elements in ascending order. How would you sort in descending order?
Solution 2
This is a simple one as well. You just need to swap the ascending comparator with a descending one when you create the SortingHeap. Looking at how ascending is defined, you can easily come up with a descending:
val descending = Comparator { first: Int, second: Int ->
when {
first < second -> 1
first > second -> -1
else -> 0
}
}
"Heap sort descending" example {
val array = arrayListOf(6, 12, 2, 26, 8, 18, 21, 9, 5)
array.heapSort(descending)
print(array)
}
---Example of Heap sort descending---
26, 21, 18, 12, 9, 8, 6, 5, 2
Key points
- Heap sort leverages the max-heap data structure to sort elements in an array.
- Heap sort sorts its elements by following a simple pattern: swap the first and last element, perform a
sift-down, decrease the array size by one; then repeat. - The performance of heap sort is O(n log n) for its best, worse and average cases.