[정렬] 힙 정렬 (수정) :: 늦깎이 IT

---

이 포스팅은 이전에 정리했던 "힙 정렬"에 대해서 핵심적인 부분만을 다시 작성한 포스팅입니다. 

[이전 포스팅]

2019/02/16 - [알고리즘 이론] - 우선순위 큐와 힙

2019/02/16 - [알고리즘 이론] - [정렬] 힙 정렬 :: 늦깎이 IT

---

[힙이란?]

힙은 최대값 및 최소값을 찾아내는 연산을 빠르게 하기 위해 [ 완전이진트리 ]를 기본으로 한 자료구조이다. 

1. 최대 힙 (Max Heap)

부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙을 "최대 힙"이라고 부른다.

2. 최소 힙(Min Heap)

부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙을 "최소 힙"이라고 부른다.

3. 힙의 형태

힙은 아래 그림처럼 한 노드가 최대 두 개의 자식 노드를 가지면서, 마지막 레벨을 제외한 모든 레벨에서 노드가 꽉 채워진 완전이진트리이다. 또한 마지막 레벨의 단말 노드들은 왼쪽부터 저장되어 있다.

[힙을 배열로 표현하기]

힙은 위의 그림처럼 완전이진트리이므로 배열로 표현할 수 있다.

아래 그림을 살펴보면 부모 노드와 자식노드간의 관계는 다음과 같이 나타낼 수 있다.

※ 인덱스가 1부터 시작할 경우에 한정한다.

루트 노드 A[1] A[i]의 부모노드 = A[i/2] A[i]의 왼쪽자식 = A[2*i] A[i]의 오른쪽자식 = A[2*i + 1]

[힙 만들기]

주어진 완전 이진트리를 최소 / 최대 힙으로 만드는 연산을 대체로 Heapify라고 부른다. 아래 그림이, 최대 힙을 나타내는 완전 이진트리라고 가정하자.

맨 왼쪽의 트리에서 루트 노드의 값이 4이므로 모든 부모 노드의 키 값은 자식 노드들의 키 값보다 크다는 조건을 만족시키지 못하므로, 최대 힙이라고 할 수 없다. 이러한 완전이진트리를 힙으로 바꾸는 것을 Heapify라고 한다.

위의 그림에서 처음에는 4와 14의 위치를 바꾸고, 그 다음으로 4와 8의 위치를 바꾸면 최대힙 조건을 만족하게 된다.

[의사 코드]

BUILD-MAX-HEAP(A)
    length ← length of A[]
    for i ← length / 2 down to 1
        do MAX-HEAPIFY(A, i)
 
 
MAX-HEAPIFY(A, i) // 노드 i를 루트로 갖는 서브트리를 Heapify하는 함수
    if there is no child of A[i]
        return
    k ← index of the bigger child of i
    if A[i] >= A[k]
        return
    swap A[i] and A[k]
    MAX-HEAPIFY(A, k)
 

3)번 루프에서 N/2 부터 1까지의 노드를 기준으로 Heapify를 수행한다.

8)번 라인에서 현재 Heapify를 진행하는 루트노드가 단말 노드이면 종료한다.

10)번 라인에서 현재 루트 노드의 자식 노드들 중 가장 큰 값을 갖는 자식 노드를 가리킨다.

11)번 라인에서 루트 노드의 값이 자식 노드보다 작다면 위치를 바꾼다.

14)번 라인에서 Heapify 함수를 재귀호출한다.

[JAVA 코드]

public static void buildMaxHeap(int[] arr, int length) {
 
        for (int i = length / 2 - 1; i >= 0; i--) {
            heapify(arr, i, length);
        }
    }
 
public static void heapify(int[] arr, int parent, int length) {
 
        // 자식 노드가 없는 경우
        if (parent * 2 + 1 >= length)
            return;
 
        //자식 노드들 중, 더 큰 자식노드 찾기
        int child = parent * 2 + 1;
        if (child + 1 < length && arr[child] < arr[child + 1])
            child += 1;
 
        //부모노드 < 자식노드 일 경우 위치를 바꿔줌
        if (arr[parent] < arr[child]) {
            int temp = arr[parent];
            arr[parent] = arr[child];
            arr[child] = temp;
        }
        heapify(arr, child, length);
 
    }

[시간 복잡도]

Heapify를 진행하는 노드는 N/2부터 1까지이다. 그 이유는 단말 노드에 대해서는 Heapify를 진행할 필요가 없기 때문이다. 

위 그림에서 Heapify를 수행하기 위해 4와 14를 바꾸고, 다시 4와 8을 바꾸는 연산을 했다. 

이처럼 어느 한 루트노드 i에 대하여 Heapify를 수행하면 i와 위치를 바꾼 자식 노드 k에 대해서도 Heapify를 수행해야한다.

즉, 트리의 높이를 h라고 했을 경우 Heapify의 시간 복잡도는 O(h)이며 트리의 높이 h는 logN으로 나타낼 수 있기 때문에 O(logN)으로 표현할 수 있다. 이를 시간 복잡도 식으로 나타내면 다음과 같다.

T(N) = N/2 * logN = O(NlogN)

N/2개의 노드에 대해서 각각 Heapify를 진행하므로 N/2 * logN으로 나타낼 수 있긴하지만 실제로는 이보다 더 적은 시간이 걸린다.  아래 그림을 보자

모든 레벨에 모든 노드가 완전히 차있는 정이진트리가 있다고 가정하자. 루트노드부터 인덱스를 매기면 트리의 마지막 레벨의 맨 오른쪽 노드의 인덱스는 N으로 표현할 수 있다. 이때, 인덱스 N의 노드 입장에서 Heapify를 수행하면 시간복잡도는 어떻게 될까? 인덱스가 N인 노드는 단말 노드이므로 O(0)의 시간이 걸린다.

마지막 레벨을 L이라고 했을 때, 레벨 L에 있는 모든 노드들의 Heapify 시간 복잡도는 O(0) * N/2만큼의 시간이 걸린다. 같은 방식으로 L-1 레벨에 있는 노드에서의 Heapify 시간 복잡도는 O(1)이고, 레벨 L-1에 있는 모든 노드들의 Heapify 시간 복잡도는 O(1) * N/4만큼의 시간이 걸린다. 이를 수식으로 나타내면 아래와 같다.

즉, 크기가 N인 데이터를 힙으로 변환하는 시간 복잡도는 O(N)만큼의 시간이 걸리게 된다.

[힙 정렬]

1. 주어진 데이터를 힙으로 변환한다.

2. 힙에서 최대 값(루트)를 가장 마지막 값과 바꾼다.

3. 힙의 크기가 1 줄어든 것으로 간주한다. 즉, 가장 마지막 값은 힙의 일부가 아닌 것으로 간주한다.

4. 루트노드에 대해서 Heapify를 진행한다.

[의사 코드]

HEAP-SORT(A)
    BUILD-MAX-HEAP(A)
    for i ← length of A down to 2 
        swap A[1] and A[i]
        length ← length - 1
        MAX-HEAPIFY(A,1)
 

2)번 라인에서 주어진 데이터를 힙으로 변환한다.

3)번 라인에서 데이터의 마지막 값부터 두 번째 값까지 반복을 실행하면서 루트노드와 자리를 바꾼후 루트노드에 대해서 Heapify를 수행한다.

[JAVA 코드]

public static void heapSort(int[] arr, int length) {
 
        buildMaxHeap(arr, length);
 
        for (int i = length - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, 0, i - 1);
        }
    }

[시간 복잡도]

힙 정렬의 시간 복잡도는 다음과 같이 나타낼 수 있다.

T(N) = O(N) + O(NlogN) = O(NlogN)

이는 주어진 데이터를 힙으로 변환하는 시간 O(N)과 N번의 루트노드에서 Heapify를 하는 시간 O(NlogN)을 더한 값이 됩니다.

[참고]

[이미지 출처]

[ratsgo's blog]