Heapsort.swift

//  heapsort.swift
//
//  Created by Michael Rockhold on 10/4/19.
//  Copyright © 2019 Michael Rockhold. All rights reserved.
//

import Foundation

extension MutableCollection where Self.Index == Int {
    
    typealias Comparator = (Self.Element, Self.Element) -> Bool

    mutating func heapsort(comparator:Comparator) {
        
        // Build the heap in array a so that largest value is at the root
        heapify(comparator)

        var end = endIndex - 1
        while end > startIndex {
            // a[0] is the root and largest value. The swap moves it in front of the sorted elements.
            swapAt(end, startIndex)
            // the heap size is reduced by one
            end -= 1
            // the swap ruined the heap property, so restore it
            siftDown(start: startIndex, end: end, comparator: comparator)
        }
    }
    
    private mutating func heapify(_ comparator: Comparator) {
        
        func parent(_ i: Self.Index) -> Self.Index {
            
            let sliceIndex = i - startIndex
            return startIndex + (Int(floor(Float(sliceIndex-1))))
        }

        // Build the heap in array a so that largest value is at the root
        // start is assigned the index in 'a' of the last parent node
        // find the parent of the last element
        var start = parent(endIndex-1)
        
        while start >= startIndex {
            // sift down the node at index 'start' to the proper place such that all nodes below
            // the start index are in heap order
            siftDown(start: start, end: endIndex-1, comparator: comparator)
            // go to the next parent node
            start -= 1
        }
        // after sifting down the root all nodes/elements are in heap order
    }
                
    // Repair the heap whose root element is at index 'start', assuming the heaps rooted at its children are valid
    mutating private func siftDown(start: Self.Index, end: Self.Index, comparator: Comparator) {
        
        func leftChild(_ i: Self.Index) -> Self.Index {
            let sliceIndex = i - startIndex
            return startIndex + (2 * sliceIndex + 1)
        }
        
        func compareAt(_ ia: Self.Index, _ ib: Self.Index) -> Bool {
            return comparator(self[ia], self[ib])
        }
        
        var root = start
        
        while leftChild(root) <= end {          // While the root has at least one child
            let child = leftChild(root)         // Left child of root
            var swap = root                     // Keeps track of child to swap with
            
            if compareAt(swap, child) {
                swap = child
            }
            // If there is a right child and that child is greater
            if child+1 <= end && compareAt(swap, child+1) {
                swap = child + 1
            }
            if swap == root {
                // The root holds the largest element. Since we assume the heaps rooted at the
                // children are valid, this means that we are done.
                return
            } else {
                swapAt(root, swap)
                root = swap                     // repeat to continue sifting down the child now)
            }
        }
    }
}

func test_heapsort() {
    
    var bh3 = (0...99).map { $0 }
    bh3.shuffle()
    bh3.heapsort{ (a, b) in a < b }
    bh3.heapsort{ (a, b) in a < b }
    bh3.append(22)
    bh3.heapsort{ (a, b) in a < b }
    
    bh3.heapsort{ (a, b) in a >= b }
    
    bh3[5...16].heapsort { (a, b) in a < b }
    
    var bh2 = ["dog", "cat", "apple", "moon", "egg"]
    bh2.heapsort { (a, b) in a < b }
    
    bh2.heapsort { (a, b) in a >= b }
}

An implementation of Heapsort in Swift, slavishly following the pseudocode example at https://en.wikipedia.org/wiki/Heapsort.

The approach here creates an extension to the MutableCollection protocol; any data structure (eg Array) that implements that protocol (so long as it uses Int for indexing) now has a 'heapsort()' method that takes a comparison function as the argument.

This example is framed as an extension on the MutableCollection protocol rather than something more concrete, so that we carry out heapsort on a wider range of collections, in particular array slices. Note on line 100 we demonstrate this, by doing a min-heap sort in-place of a short stretch of the same array that we had just done a max-heap sort in line 98.