• 최댓값이나 최솟값을 찾아내는 연산을 빠르게하기 위해 구현된 완전 이진트리를 기본으로한 정렬 방식임.
  • 힙(Heap)이란 데이터에서 최댓값과 최솟값을 빠르게 찾기 위한 트리 자료구조임.
    • 이는 완전 이진 트리를 기반으로 함.
• 내림차순은 최소 힙, 오름차순은 최대 힙을 구성하면 됨.
  • 최소 힙 : 루트 노드가 가장 작은 값
    • 자식 노드보다 부모 노드가 작아야 함.
  • 최대 힙 : 루트 노드가 가장 큰 값
    • 자식 노드보다 부모 노드가 커야 함.
• 힙 정렬을 하기 위해선 정해진 데이터를 힙 구조로 만들어야 함.
  • 최대, 최소 힙에 따라 자식노드 > 부모노드 or 자식노드 < 부모노드
• 불안정 정렬임.

알고리즘

• n개의 노드에 대한 완전 이진 트리를 구성함.
  • 구성 방법은 루트 노드부터 왼쪽 자식노드, 오른쪽 자식 노드로 구성.
• 최대 힙을 구성. 단말 노드를 자식 노드로 가진 부모 노드부터 구성하여 아래부터 루트까지 올라오며 순차적으로 만듦.
  • 최대 힙 : 부모노드가 자식노드보다 큰 트리
  • 단말 노드 : 자식이 없는 노드(Leaf Node)
• 가장 큰 수(루트에 위치)를 가장 리프 노드와 교환.
  • 루트 노드의 값은 배열의 뒤 부터 저장함.
  • 힙의 크기를 줄이고, 다시 최대 힙을 구성하는 것.

예시

정렬되지 않은 배열로 가정하고, 오름차순으로 정렬 프로세스로 가정. → [6, 5, 3, 1, 8, 7, 2, 4, 9]

      	 6
      /     \\
     5       3
   /   \\   /   \\
  1     8 7     2
 / \\
4   9

1. 최대 힙 구조 만들기

	       9
      /     \\
     8       7
   /   \\   /   \\
  6     5 3     2
 / \\
1   4

1. 정렬

	       **4**
      /     \\
     8       7
   /   \\   /   \\
  6     5 3     2
 / \\
1   **9**

• 루트 노드와 가장 마지막 리프 노드를 바꿔준 후 바꿔준 원소(9)를 제외하고 다시 힙 구조를 만듦.

	       8
      /     \\
     6       7
   /   \\   /   \\
  4     5 3     2
 / \\
1   9

• 이 연산을 반복하면 원소들이 오름, 내림 차순으로 정렬이 됨.

소스코드 - Kotlin

fun main() {
    val array = intArrayOf(4, 2, 6, 3, 7, 8, 5, 1)
    heapSort(array)
}

fun heapify(array: IntArray, n: Int, i: Int) {
    var p = i
    val l = i * 2 + 1
    val r = i * 2 + 2

    if (l < n && array[p] < array[l]) {
        p = l
    }
    if (r < n && array[p] < array[r]) {
        p = r
    }
    if (i != p) {
        swap(array, p, i)
        heapify(array, n, p)
    }
}

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

    // init, max heap
    // 힙 구조는 O(n)번이면 만들 수 있음. 전체 개수의 반만 보면됨
    // 그 이유는 절반의 노드 개수로도 힙 구조를 생성하기 때문임.
    // 힙 구조를 충족하지 못할 경우엔, 부모 노드까지 타고 올라감.

    for (i in n / 2 - 1 downTo 0) {
        heapify(array, n, i)
    }

    // for extract max element from heap
    for (i in n - 1 downTo 1) {
        swap(array, 0, i)
        heapify(array, i, 0)
    }
}

fun swap(array: IntArray, a: Int, b: Int) {
    val temp = array[a]
    array[a] = array[b]
    array[b] = temp
}