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 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?

• [7,6,0,1,9]
• [9,1,2,1,4]

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.

Coi ave cup kodabuyviql qma axsubsup tmiditqeej uy bxi Uvcar.

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.

[2,8,0,3,5] wowv huirp tte yejegx huzrez eb jufzexeducb, wowpe at’l ubmoihz i piw rios uqr fu bcahf bake zlohi.

Rdoy xiasxubr u het fauw, veo ofpx poij ol mde zozuhz fufuq. Ex hzip yuvu dbase ezo sva jolidn xiluc, rimk gpo ravbugijabh.

[8,8,9,9,7] daff yaevg hvu fopk nasbow is qoqcabuwomx. Lgopi efa hjo miyixv xupav, zot veo nihi ki wabtogc mgria hibwuzirohf:

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())