(5) 힙 정렬법 (Heap Sorting)

(5) 힙 정렬법 (Heap Sorting)

먼저 힙 정렬을 이해하기 위하여 히프라는 자료구조를 정의한다. 이진 트리를 기억공간에 저장
할 때 일차원 배열을 사용한다. 일차원 배열의 i번째 위치한 노드의 부모 위치는 i/2 이고 왼쪽
자식노드가 있다면 2*i 위치에 있으며 오른쪽 자식 노드가 있다면 2*i+1의 위치에 존재한다(i/2
는 i/2의 결과에서 소수점 이하의 자리수를 버림). 역으로 일차원 배열에 저장된 키값은 이러한
위치 공식에 의하여 이진 트리로 간주될 수 있다. 히프는 다음의 성질을 만족하는 이진 트리이다.

1. 히프는 완전 이진 트리이다.
2. 루트의 키값은 부분 트리의 노드의 키값보다 크거나 같다.
3. 왼쪽 부분 트리와 오른쪽 부분 트리 역시 위 2의 성질을 만족한다.

그림 7은 위의 성질을 만족하는 히프와 일차원 배열에 이러한 히프를 저장한 예를 보여준다.

(그림 7) 히프의 예와 일차원 배열에 저장된 형태

노드를 저장하는 위치를 사용하여 히프의 성질 2를 다시 정의하면 K[i]>=K[2*i] (단 2*i
<=n)이고 K[i]>=K[2*i+1] (단 2*i+1<=n)으로 나타낼 수 있다. 그림 7에서 이러한 성질
이 만족됨을 알수 있다. (이 정의는 최대 히프(max heap)를 나타내며 부등호가 반대 방향이고
최소 히프(min heap)를 나타낸다.)
히프 정렬은 두 단계로 나누어 실행되는데 먼저 정렬하고자 하는 리스트를 히프 구조로 만들고
히프 구조에서 정렬을 수행한다. adjust는 어느 한 노드 x에서 x를 루트로 하는 트리에서 이미
히프가 이 성질을 만족하는 오른쪽 부분 트리와 왼쪽 부분 트리를 조정하여 x를 포함하는 트리 전
체가 히프가 되도록하는 알고리즘이다. 예를 들면 그림 8과 같은 트리를 살펴보자.

(그림 8) adjust 알고리즘을 위한 예

그림 8에서 x로 표시된 노드를 루트로 하는 부분 트리는 현재 히프 구조가 아니나 그 노드의 왼
쪽부분 트리는 각각 히프의 성질을 만족한다. 이때 노드 x를 시작 노드로 하여 왼쪽 자식과 오른
쪽 자식을 비교하여 더 큰 노드를 선택, 노드 x와 비교한다. 노드 x가 크면 adjust 알고리즘을
멈추고 노드x가 작다면 두 노드를 교환하여 교환된 자식 노드에서 이러한 과정을 반복한다. 그림
8의 예에서 과정이 반복되는 것을 보이면 그림 9와 같다.

(그림 9) adjust 알고리즘의 적용 예

위에서 설명된 adjust 알고리즘을 수행하면 노드 x를 루트로 하는 부분 트리 전체가 히프 구조로
된다. 이때 노드 x의 위치가 i이면 왼쪽 자식의 위치는 2*i이고 오른쪽 자식의 위치는 2*i+1임
에 유의하여 adjust 알고리즘을 작성하면 리스트 10과 같다.

(리스트 10) adjust 알고리즘
void adjust(int a[], int i, int n)
{
    int j, k, done;

    done=FALSE;
    k=a[i];
    j=2*i;
    while ((j<=n)&&(!done))     /* 자식노드가 있고 not done일 때까지 반복 */
    {
        if (j<n)                 /* 오른쪽 자식노드가 존재하는가? */
            if (a[j]<a[j+1])       /* 자식노드들 중 큰 노드를 선택 */
                j=j+1;
        if (k>=a[j])
            done=TRUE;        /* 자식노드보다 크므로 반복을 중단 */
        else{
            a[j/2]=a[j];          /* 자식노드와 교환 */
            j=2*j;   }
    }
    a[j/2]=k;
}

리스트 10에서 adjust 알고리즘은 최악의 경우 시작 노드에서 가장 하위의 노드까지 비교해야
하므로 n개의 노드를 갖는 완전 이진 트리에서는 O(log₂n)시간을 필요로 한다.
히프 정렬의 첫 단계는 정렬하고자 하는 리스트를 히프 구조로 만드는 것으로 전체 노드의 수가
n개일 때 i/2 의 위치에서 시작하여 i/2 -1, i/2 -2,......,1의 위치에 있는 노드를 시작 노드로
adjust 알고리즘을 반복 수행한다. i/2 의 위치에서 시작하는 이유는 i/2 +1, i/2 +2,......,n
위치에 있는 노드들은 모두 단말 노드이므로 이미 히프 구조를 가지기 때문이다. 그림 10은 정렬
하고자 하는 키값들을 초기 히프 구조로 만드는 과정을 보여준다.

(그림 10) 초기의 히프 구조 만들기

그림 10 (b)는 n/2 번째, 즉 5번째 노드에서 adjust를 수행한 결과를 나타내며, 노드 4, 3, 2, 1
에서 차례로 adjust가 수행되었을 때 그림 10 (c)로 되어 전체 리스트가 히프 구조로 되었음을 알
수 있다.
두 번째 단계에서는 히프 구조에서 정렬을 수행하는 것으로 다음의 과정을 반복한다. 전체 트리
의 루트를 마지막 노드와, 즉 key[1]과 key[n]을 교환한 후 루트로부터 n-1개의 노드에 대하여
adjust 알고리즘을 수행한다. 방금 교환된 key[n]에 있는 노드는 adjust에서 제외됨에 유의하라.
그림 11은 그러한 과정을 보여준다.

(그림 11) 히프 정렬을 위한 첫 동작

이러한 조정이 끝나면 key[1]과 key[n-1]을 교환한 후 크기를 n-2로 하여 adjust 알고리즘
을다시 수해한다. 이러한 과정을 n-1번 수행하면 리스트의 마지막에서부터 차례로 교환된 키값
들이 정렬된 상태로 남게 된다. 그림 12는 최종 정렬이 완료되었을 때의 일차원 배열에 저장된 키
들을 보여준다.

(그림 12) 히프 정렬의 수행 결과

이러한 과정을 C 프로그램으로 작성하면 리스트 11과 같다.

(리스트 11) 히프 정렬
void Heap(int n)
{
int i, temp;

    for (i=(n/2);i>=1;--i)      /* 초기 히프 만들기 */
        adjust(key, i, n);
    for (i=(n-1);i>=1;--i)      /* 히프 정렬의 두 번째 단계 */
    {
        temp=key[i+1];        /* i개의 키에 대하여 adjust 적용 */
        key[I+1]=key[1];
        key[1]=temp;
        adjust(key, 1, I);
    }
}

히프 정렬의 분석

리스트 11에서 첫 번째 for문은 정렬할 리스트를 초기 히프 구조로 만드는 부분이며 O(n)시간
이 걸린다고 알려져 있다. 그리고 두 번째 for문은 히프 정렬의 두 번째 단계를 위한 것으로 총
n-1번의 교환과 adjust 알고리즘을 수행하므로 한 번의 adjust 알고리즘이 최악의 경우
O(log₂n)시간이 소요되어 총 O(nlog₂n)시간이 걸림을 알 수 있다. 따라서 히프 정렬을 위한
시간은 O(nlog₂n)이 된다.