import Foundation

//参考：https://www.programiz.com/dsa/heap-sort

func heapSort(array:inout [Int]) {
    //构建最大堆，从完全二叉树的最后一个非叶子节点往前作堆化；最后一个非叶节点的索引是：(n/2 - 1)
    var i = array.count/2 - 1
    while i >= 0 {
        //堆化
        heapify(array: &array, n: array.count, i: i)
        i -= 1
    }
    
    //堆排序，遍历所有的节点，依次拿根节点的值与它互换；
    //因为每次取根节点的值互换后都会重新堆化，所以每次取的值都是新堆里最大的，当迭代完成后其实就完成了数组的重排
    var j = array.count - 1
    while j >= 0 {
        //值互换，依次把根节点值交换到非叶子节点处
        array.swapAt(0, j)
        
        //在大小为j的堆上再次做堆化处理，以期下次在根位置(0)处获得的值，仍然是这个大小为j的堆里最大的
        heapify(array: &array, n: j, i: 0)
        
        j -= 1
    }
}

//堆化，是自顶向下(从根到叶子)把底层的大值交换到顶层的迭代过程
func heapify(array:inout [Int], n:Int, i:Int) {
    //假设默认i指向是当前堆的最大值，定义一个largest指针指向最大值
    var largest: Int = i
    
    //则左右孩子指针分别为left、right
    let left = 2 * i + 1
    let right = 2 * i + 2
    
    //如果左指针left在当前堆大小n的范围内，并且left所指的值大于前最大值
    if left < n && array[left] > array[largest] {
        largest = left //赋值largest指向左指针位置，largest指向发生变化
    }
    //如果右指针right在当前堆大小n的范围内，并且right所指的值大于前最大值
    if right < n && array[right] > array[largest] {
        largest = right //赋值largest指向右指针位置，largest指向发生变化
    }
    
    //如果largest指向发生变化，不再是默认i指的位置了
    if largest != i {
        //交换array[i]与array[largest]的值
        array.swapAt(i, largest) //因i是left与right的父节点，这个交换操作保证了父节点的值大于子节点的
        
        //因为在这个if里largest是已经被赋值指向了子节点，所以继续递归对子节点作堆化处理
        heapify(array: &array, n: n, i: largest)
    }
    
}

//打印
func printHeapSortSort(_ array:inout [Int]){
    heapSort(array: &array)
    print(array)
}

var arr:[Int] = [3, 2, 5, 7, 1, 5, 4, 8, 11, 0]
printHeapSortSort(&arr)