33.堆排序挑战

挑战1：给Array添加堆排序

给Array添加一个heapSort()方法。这个方法应该按升序对数组进行排序。启动模板在启动程序的playground上。

挑战2：理论

当按升序进行堆排序时，这些起始数组中哪一个需要的比较次数最少？

• [1,2,3,4,5]
• [5,4,3,2,1]

挑战3：降序

第32章中的堆排序的当前实现是按ascending序排序的。你如何以descending排序？

解决方案

挑战1的解决方案

为了给Array添加堆排序，你必须创建一个extension，其中数组中的元素必须是Comparable。其他的事情都很简单，因为其实现与第32章中的Heap类似。

现在你正在引用Array的内部属性。

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

挑战2的解决方案

使用堆排序对元素进行升序排序时，首先需要一个最大堆。你需要看的是构建最大堆时发生的比较次数。

[5,4,3,2,1]将产生最少的比较次数，因为它已经是一个最大堆，并且没有发生交换。

当建立一个最大堆时，你只看父节点。在这个例子中，有两个父节点有两个比较。

[1,2,3,4,5]将产生最多的比较次数。有两个父节点，但你必须进行三次比较：

挑战3的解决方案

只需在排序前使用最小堆而不是最大堆：

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