힙 정렬

1. 개념

• 힙 : 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된, 완전 이진 트리를 기본으로 한 자료구조
  • 완전 이진 트리 : 부모 노드 밑에 자식 노드가 최대 2개까지 있을 수 있고, 마지막 레벨을 제외한 모든 레벨에 노드가 완전히 채워져 있는 트리 구조
• 최대 힙 : 부모 노드가 자식 노드보다 항상 크거나 같은 트리
• 최소 힙 : 부모 노드가 자식 노드보다 항상 작거나 같은 트리
• 힙 정렬 : 최대 힙 트리나 최소 힙 트리를 구성해 정렬하는 알고리즘

2. 구현 (kotlin)

fun heapify(array: IntArray, index: Int, heapSize: Int) {
    // 부모 노드와 자식 노드의 인덱스 지정
    var parent = index
    val leftChild = parent * 2 + 1
    val rightChild = parent * 2 + 2

    // 왼쪽과 오른쪽 자식 노드 중 더 큰 노드의 인덱스를 부모 노드의 인덱스로 지정한다.
    if (leftChild < heapSize && array[leftChild] > array[parent]) {
        parent = leftChild
    }
    if (rightChild < heapSize && array[rightChild] > array[parent]) {
        parent = rightChild
    }

    // 자식 노드 중 더 큰 노드와 부모 노드를 교환한다.
    if (parent != index) {
        val temp = array[parent]
        array[parent] = array[index]
        array[index] = temp
        heapify(array, parent, heapSize) // 힙을 재구조화한다.
    }
}

fun main() {
    val array = intArrayOf(1, 3, 5, 7, 9, 2, 4, 6, 8, 10)
    val size = array.size

    for (i in (size - 1) / 2 downTo 0) { // 부모 노드가 되는 노드만을 골라서 뒤에서부터 heapify 적용
        heapify(array, i, size)
    }

    // 힙정렬 수행
    for (i in size - 1 downTo 0) {
        val temp = array[0]
        array[0] = array[i]
        array[i] = temp
        heapify(array, 0, i - 1)
    }

    array.forEach {
        print("$it ")
    }
}

3. 정렬 과정

• 입력된 배열을 최대 힙으로 재구성
  
  

• 힙 정렬
  
  

4. 시간복잡도

• 입력된 배열을 최대 힙으로 구성하는 시간복잡도 O(n)
• 마지막 노드가 루트 노드에 올라오기 까지 트리의 높이(logn)만큼 자리를 이동해야 한다. 이런 노드들이 n개 있으므로 O(nlogn)

→ O(n) + O(nlogn) = O(nlogn)

면접 예상 질문

1. 최대 힙과 최소 힙을 비교하여 설명해주세요.
2. 힙 정렬을 구현해주세요.

참고 URL

https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)
https://ko.wikipedia.org/wiki/%ED%9E%99_%EC%A0%95%EB%A0%AC
https://yozm.wishket.com/magazine/detail/2312/
https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-%ED%9E%99Heap