힙 정렬

func heapify(array: inout [Int], index: Int, size: Int){
    var largest: Int = index
    let leftIndex = index * 2 + 1
    let rightIndex = index * 2 + 2
    if(leftIndex < size && array[leftIndex] > array[largest]){
        largest = leftIndex
    }
    if(rightIndex < size && array[rightIndex] > array[largest]){
        largest = rightIndex
    }
    if(largest != index){
        let temp = array[largest]
        array[largest] = array[index]
        array[index] = temp
        heapify(array: &array, index: largest, size: size)
    }
}
 
func heapSort(array: inout [Int]){
    let size = array.count
    for i in stride(from: size / 2 - 1, through: 0, by: -1){
        heapify(array: &array, index: i, size: size)
    }
    for i in stride(from: size - 1, through: 0, by: -1){
        let temp = array[0]
        array[0] = array[i]
        array[i] = temp
        heapify(array: &array, index: 0, size: i)
    }
}

heapify 함수는 주어진 인덱스부터 트리를 타고 내려가면서 힙 성질을 만족하게 하는 함수이다.

heapSort 함수의 첫 번째 for문에 의하여 max heap이 만들어지고 내림차순 정렬이 된다.

아래의 for문에 의해 오름차순 정렬된 결과가 나온다.