This article is a translation of Swift Algorithm Club.

Swift Algorithm Club is an open source project produced by Raywenderlich.com to realize algorithms and data structures by Swift. Currently, there are 18000+⭐️ on GitHub. I have made a brief statistics, and there are about 100 algorithms and data structures. It’s basically a good resource for iOSer learning algorithms and data structures.

🐙andyRon/ swift-algorithm-club-CN is my project of learning and translating for Swift Algorithm Club. Due to the limited capacity, if you find any errors or improper translation, please correct them. Welcome to Pull Request. Also welcome interested, have time partners to participate in translation and learning 🤓. Of course, we welcome ⭐️, 🤩🤩 ️ ⭐ ⭐.

A translation of this article and the code can be found at 🐙swift-algorithm-club-cn/Heap Sort

Heap Sort

Sort arrays from lowest to highest using a heap. (Also from highest to lowest)

A heap is a partially sorted binary tree stored in an array. The heapsort algorithm uses the structure of the heap to perform quicksort.

To sort from lowest to highest, heapsort first converts the unsorted array to max-heap so that the first element in the array is the largest.

Suppose that the array to be sorted is:

[5, 13, 2, 25, 7, 17, 20, 8, 4]Copy the code

It first becomes a max-heap as shown below:

The array of the heap is:

[25, 13, 20, 8, 7, 17, 2, 5, 4]Copy the code

It’s hardly desirable to sort from low to high!

Now to sort: we swap the first element (index 0) with the last element of index n-1 to get:

[4, 13, 20, 8, 7, 17, 2, 5, 25] * *Copy the code

The new root node 4 is now smaller than its children, so we use Shift down or “heapify” to restore the 0 to n-2 elements to max-heap. After fixing the heap, the new root node is now the second largest item in the array:

[20, 13, 17, 8, 7, 4, 2, 5 | 25]
Copy the code

Important note: When we fix the heap, we ignore the last item with index N-1. The last item is the maximum in the array, so it’s already in the final sort position. | bar said array sorted part of the starting position. From now on, we will separate in addition to the rest of the array (| front part).

Again, we swap the first element with the last (this time in index n-2) :

[5, 13, 17, 8, 7, 4, 2, 20 | 25]
 *                      *
Copy the code

And fix the heap to make it effective max-heap again:

[17, 13, 5, 8, 7, 4, 2 | 20, 25]
Copy the code

As you can see, the largest item is moving backwards. We repeat this process until we reach the root node, which sorted the entire array.

Note: This procedure is very similar to selection sort in that it repeatedly looks for the smallest item in the rest of the array. Extracting the minimum or maximum is what the heap is good at doing.

Heapsort performs best, worst and average O(n lg N). Because we modify the array directly, we can perform heap sort in place. But it is not a stable type: the relative order of the same elements is not preserved.

Here is how to implement heap sort in Swift:

extension Heap {
  public mutating func sort(a)- > [T] {
    for i in stride(from: (elements.count - 1), through: 1, by: -1) {
      swap(&elements[0], &elements[i])
      shiftDown(0, heapSize: i)
    }
    return elements
  }
}
Copy the code

A sort() function was added for the heap implementation. This function can be used as follows:

var h1 = Heap(array: [5.13.2.25.7.17.20.8.4].sort: >)
let a1 = h1.sort(a)Copy the code

Since we need a Max-heap to sort from low to high, you need to provide the reverse sort function for the heap. To sort <, you must create Heap objects using > as the sort function. In other words, sorting from low to high creates a Max-heap and converts it to a min-heap.

We can write a handy helper function for this:

public func heapsort<T>(_ a: [T], _ sort: @escaping (T, T) -> Bool) - > [T] {
  let reverseOrder = { i1, i2 in sort(i2, i1) }
  var h = Heap(array: a, sort: reverseOrder)
  return h.sort()}Copy the code

Usage:

let a2 = heapsort([5.13.2.25.7.17.20.8.4], <)
print(a2)
Copy the code

Translated by Andy Ron proofread by Andy Ron