[Algorithm] 정렬 알고리즘에 대하여 3

안녕하세요, Einere입니다.

(ADblock을 꺼주시면 감사하겠습니다.)

 

2019/06/26 - [programing/Algorithm] - [Algorithm] 정렬 알고리즘에 대하여 1

2019/06/27 - [programing/Algorithm] - [Algorithm] 정렬 알고리즘에 대하여 2

---

이번 포스트에서는 이진 힙(binary heap)를 이용한 힙(heap) 정렬에 대해 알아보도록 하겠습니다.

 

 

 

힙 (heap)

힙은 다음과 같은 성질을 지니고 있습니다.

• 완전 이진 트리 (complete binary tree)
  • 모든 노드는 최대 두 개의 자식을 가질 수 있습니다.
  • 모든 잎 노드 (leaf node)의 깊이(depth)는 동일하며, 왼쪽부터 빈틈없이 채워져야 합니다.
  • 모든 잎 노드를 제외한 깊이의 노드는 꽉 찬 트리(full tree)여야 합니다.
• 힙 성질 (heap property)
  • 최대 힙 성질 (max heap property) : 부모는 무조건 자식 이상의 값을 가진다.
  • 최소 힙 성질 (min heap property) : 부모는 무조건 자식 이하의 값을 가진다.

따라서, 힙에는 최대 힙과 최소 힙이 있습니다. (동시에 두 성질을 만족할 수 없습니다.)

포스트에서는 최대 힙을 예로 들어 설명하도록 하겠습니다.

 

힙을 1차원 배열로 표현하는 방법

또한 힙은 완전 이진트리의 특성을 이용해, 링크드 리스트가 아닌 1차원 배열로 간단히 구현할 수 있습니다. 단, 인덱스를 0부터 시작하도록 한다면 계산이 조금 복잡해집니다.

 

재힙화 (reheapification)

최대 힙의 경우, 부모는 자식 이상의 값을 가져야 한다고 했습니다. 따라서, 힙이 아닌 트리를 힙으로 만드는 것을 재힙화라고 합니다.

재힙화에는 상향 재힙화(upward reheapification)과 하향 재힙화(downward reheapification)이 있습니다.

상향 재힙화는 트리에 노드를 추가했을 때 해당 노드가 제 자리를 찾을 때 사용하며, 하향 재힙화는 루트 노드를 제거했을 때 마지막 노드를 루트노드로 옮긴 뒤 제자리로 찾을 때 사용합니다.

 

 

코드

// 계산의 편의를 위해 1-base 배열을 사용하며, 0번 인덱스는 비워놓습니다.
void reheapify(int[] arr, int start, int end) {
    if (start > end) return;

    // 왼쪽 자식 노드가 존재하는 경우
    if (2 * start <= end) {
        int maxChildValue = arr[2 * start];
        int maxChildIndex = 2 * start;

        // 오른쪽 자식 노드도 존재하는 경우
        if (2 * start + 1 <= end && maxChildValue < arr[2 * start + 1]) {
            maxChildValue = arr[2 * start + 1];
            maxChildIndex = 2 * start + 1;
        }

        // 자식이 값이 더 크다면 부모와 값을 교환
        if (maxChildValue > arr[start]) {
            int tmp = arr[start];
            arr[start] = maxChildValue;
            arr[maxChildIndex] = tmp;
        }
    }

    // 다음 노드에 대해 재힙화 진행
    reheapify(arr, start + 1, end);
}

위는 각 노드에 대해, 자식 노드의 값과 비교하여 더 큰 값을 가진 노드를 부모로 만드는 함수입니다.

위 함수는 하향 재힙화입니다.

 

void makeHeap(int[] arr) {
    // 제일 마지막 가지(branch) 노드부터 힙화를 진행한다.
    // 즉, 맨 마지막 잎 노드의 부모부터 진행한다.
    // 0번 인덱스는 비워뒀으므로, -1을 해준다.
    int index = (arr.length - 1) / 2;

    // 뿌리(root) 노드까지 진행한다.
    for (int i = index; i > 0; i--) {
        reheapify(arr, i, arr.length - 1);
    }
}

만약, 임의의 배열에 대해 힙으로 만들고 싶다면 위 함수를 실행하면 됩니다.

위 함수는 상향 재힙화입니다.

 

 

 

대표적인 정렬 알고리즘

힙 정렬 (heap sort)

힙 정렬은 이진 힙을 이용하여 정렬을 합니다.

분할 정복 기법을 이용한 병합 정렬과는 달리, 추가적인 메모리가 불필요하다는 장점이 있습니다.

힙의 뿌리 노드는 최대값을 가진다는 특성을 이용하여, 뿌리 노드(배열의 1번)와 마지막 잎 노드(배열의 마지막)를 교한한 후, 마지막 잎 노드를 제외한 노드에 대해서 재힙화를 진행합니다. 이렇게 반복하면 결국엔 오름차순으로 정렬됩니다.

 

 

코드

void heapSort(int[] arr) {
    // 힙으로 만들어줍니다.
    makeHeap(arr);

    // 정렬합니다.
    for (int i = arr.length - 1; i > 0; i--) {
        // 뿌리 노드와 마지막 잎 노드를 교환합니다.
        int tmp = arr[1];
        arr[1] = arr[i];
        arr[i] = tmp;

        // 마지막 노드를 제외하고 하향 재힙화를 진행합니다.
        reheapify(arr, 1, i - 1);
    }
}

우선 최대 힙의 특성상, 뿌리 노드는 최대값입니다. 이 뿌리 노드를 배열의 마지막 원소인 마지막 잎 노드와 교환합니다. 그리고 마지막 원소를 제외한 배열에 대해 하향 재힙화를 진행합니다.

이것을 배열에서 모든 요소를 제외할 때 까지 반복합니다.

 

 

시간복잡도

• 힙화 시간복잡도 : T(n) = O(n)
• 정렬반복 시간복잡도 : T(n) = n-1
• 재힙화 : T(n) = 1+1+...+1 = O(logn)
  • 이진 완전 트리이므로, 높이는 최대 logn이다.

T(n) = O(n) + (n-1) * O(logn) = O(nlogn)

 

• 최악 : O(nlogn)
• 평균 : 
• 최선 :