[알고리즘][Kotlin] Heap Sorting

우선순위 큐를 구현해 보았다. 힙을 이용해서 우선순위 큐를 구현했을 때 요소를 추가 삭제하는 과정에서 정렬이 이루어지는 과정을 살펴 보았다.

힙정렬은 자료구조인 힙Heap을 사용하여 정렬을 수행한다. 정렬 알고리즘 중에서 빠른 축에 속하며 시간 복잡도는 O(NlogN)이다.

힙정렬 구현

먼저 n개의 데이터가 주어질 때 힙정렬을 하기 위해서 어떻게 해야 할지 생각해 보아야 한다. 가장 먼저 떠오르는건 힙 구조에 n개의 데이터를 넣어 정렬시키는 방법이다. 하지만 이것보다 더 효율적인 방법이 있다고 한다.

바로 임의의 1차원 배열을 힙 구조로 바꾸는 것이다.

그러기 위해 두 가지 기능을 구현해야한다.

BuildHeap : 정렬되지 배열을 힙으로 만듦
Heapify : 힙 특성 유지

전체적인 흐름은 다음과 같다.

BuildHeap

private fun buildMinHeap(arr:IntArray,n:Int){
	//리프노드를 제외한 나머지 노드들을 대상으로 뒤에서 부터 heapify 수행
    for (i in n/2 downTo 1){
        heapify(arr, i, n)
    }
}

부모노드를 대상으로 heapify를 수행한다. 이때 완전 이진 트리의 특징 중 하나를 이용하는데 바로 리프노드의 개수가 전체 트리 노드 개수의 절반인 점이다.

Heapify

Heapify는 우선순위 큐에서 요소를 제거하는 기능과 같다.

1. 먼저 맨 마지막 노드를 루트노드로 옮긴다.
2. 루트노드에서 부터 오른쪽 자식 노드와 왼쪽 자식 노드를 비교하여 교환한다.
3. 자식노드로 이동한다.

private fun heapify(arr:IntArray,k:Int,n:Int){

    val left = 2*k
    val right =2*k+1
    var min = 0
    if(right<= n) {
        min = if (arr[left] < arr[right]) left else right
    } else if(left<=n) min = left;
    else return;

    // 최소 힙 성질을 만족하지 못하는 경우 재귀적으로 수정한다.
    if (arr[min] < arr[k]){
        //swap
        val temp = arr[k]
        arr[k]=arr[min]
        arr[min]=temp

        heapify(arr, min, n);
    }

전체 코드

fun main() {
    val (n,k) = readln().split(" ").map{it.toInt()}
    val arr =intArrayOf(0)+readln().split(" ").map{it.toInt()}.toIntArray()
    target=k
    buildMinHeap(arr,n)

    for (i in n downTo 2) {
        //swap
        val temp = arr[1]
        arr[1]=arr[i]
        arr[i]=temp

        heapify(arr, 1, i-1);
    }
    if(flag) println(-1)
}
private fun buildMinHeap(arr:IntArray,n:Int){
    for (i in n/2 downTo 1){
        heapify(arr, i, n)
    }
}
private fun heapify(arr:IntArray,k:Int,n:Int){

    val left = 2*k
    val right =2*k+1
    var min = 0
    if(right<= n) {
        min = if (arr[left] < arr[right]) left else right
    } else if(left<=n) min = left;
    else return;

    // 최소 힙 성질을 만족하지 못하는 경우 재귀적으로 수정한다.
    if (arr[min] < arr[k]){
        //swap
        val temp = arr[k]
        arr[k]=arr[min]
        arr[min]=temp

        heapify(arr, min, n);
    }

}

적용해보기

24173.알고리즘 수업 - 힙 정렬 1