• 데이터들을 Heap 구조로 정렬하는 방식
  • Heap이 완전 이진 트리이기 때문에 Root가 최대 또는 최소를 가지게 된다
• 시간 복잡도 : O(nlogn), 공간 복잡도 : O(1)

fun main() {
    val arr = intArrayOf(3, 2, 5, 1, 4, 6)
    heapSort(arr)
    println(arr.contentToString())
}

fun heapSort(arr: IntArray) {
    val n = arr.size

    // 초기 힙 구성: 가장 마지막 부모 노드부터 시작하여 최대 힙 구성
    for (i in n / 2 - 1 downTo 0) {
        heapify(arr, n, i)
    }

    // 요소를 하나씩 제거하면서 힙을 재구성
    for (i in n - 1 downTo 1) {
        // 최대 힙의 루트(가장 큰 값)를 배열의 마지막 요소와 교환
        arr[0] = arr[i].also { arr[i] = arr[0] }
        // 힙 크기를 줄이고, 루트 노드를 재구성하여 최대 힙 유지
        heapify(arr, i, 0)
    }
}

// i를 루트로 하는 부분 힙을 최대 힙으로 구성하는 함수
fun heapify(arr: IntArray, n: Int, i: Int) {
    var largest = i         // 최대값을 가진 노드의 인덱스 초기화
    val left = 2 * i + 1    // 왼쪽 자식 인덱스
    val right = 2 * i + 2   // 오른쪽 자식 인덱스

    // 왼쪽 자식이 현재 최대값보다 크면, 최대값 인덱스 업데이트
    if (left < n && arr[left] > arr[largest]) {
        largest = left
    }

    // 오른쪽 자식이 현재 최대값보다 크면, 최대값 인덱스 업데이트
    if (right < n && arr[right] > arr[largest]) {
        largest = right
    }

    // 최대값이 루트가 아니라면, 루트와 최대값 교체
    if (largest != i) {
        arr[i] = arr[largest].also { arr[largest] = arr[i] }
        // 변경된 노드를 루트로 하는 부분 힙 재구성
        heapify(arr, n, largest)
    }
}