# 33 Heapsort Challenges Written by Vincent Ngo

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

Add a `heapSort()` method to `Array`. This method should sort the array in ascending order. A starting template is in the starter playground.

### Challenge 2: Theory

When performing 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 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.