# 33 Heapsort Challenges Written by Vincent Ngo

You can unlock the rest of this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.

### Challenge 1: Add heap sort to `Array`

Add a `heapSort()` method to `Array`. This method should sort the array in ascending order. A template has been provided for you in the starter playground.

### Challenge 2: Theory

When performing a heapsort in ascending order, which of these starting arrays requires the fewest comparisons?

### Challenge 3: Descending order

The current implementation of heapsort in Chapter 32 sorts the elements in ascending order. How would you sort in descending order?

## Solutions

### Solution to Challenge 1

To add heap sort to `Array`, you must create an `extension`, where the elements in the array must be `Comparable`. Everything else is straightforward as the implementation is similar to the `Heap` in Chapter 32.

``````extension Array where Element: Comparable {

func leftChildIndex(ofParentAt index: Int) -> Int {
(2 * index) + 1
}

func rightChildIndex(ofParentAt index: Int) -> Int {
(2 * index) + 2
}

mutating func siftDown(from index: Int, upTo size: Int) {
var parent = index
while true {
let left = leftChildIndex(ofParentAt: parent)
let right = rightChildIndex(ofParentAt: parent)
var candidate = parent

if (left < size) && (self[left] > self[candidate]) {
candidate = left
}
if (right < size) && (self[right] > self[candidate]) {
candidate = right
}
if candidate == parent {
return
}
swapAt(parent, candidate)
parent = candidate
}
}

mutating func heapSort() {
// Build Heap
if !isEmpty {
for i in stride(from: count / 2 - 1, through: 0, by: -1) {
siftDown(from: i, upTo: count)
}
}

// Perform Heap Sort.
for index in indices.reversed() {
swapAt(0, index)
siftDown(from: 0, upTo: index)
}
}
}

``````

### Solution to Challenge 2

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.

### Solution to Challenge 3

Simply use a min heap instead of a max heap before sorting:

``````let heap = Heap(sort: <, elements: [6, 12, 2, 26, 8, 18, 21, 9, 5])
print(heap.sorted())
``````

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.

Have feedback to share about the online reading experience? If you have feedback about the UI, UX, highlighting, or other features of our online readers, you can send them to the design team with the form below: