heapsort3.swift

/// Complexity: O(log n)
public mutating func insert(_ element: Element) {
    elements.append(element)
    shiftUp(from: count - 1)
}

private mutating func shiftUp(from index: Int) {
    var child = index
    var parent = parentIndex(forChildAt: child)
    while child > 0 && sort(elements[child], elements[parent]) {
        elements.swapAt(child, parent)
        child = parent
        parent = parentIndex(forChildAt: child)
    }
}