Heap 정렬(Heap Sort) - Heap 만들기

힙 정렬의 과정

Heap 정렬이 일어나는 과정은 크게 두 단계로 나눠서 볼 수 있습니다.

1. 입력으로 받은 배열을 Heap으로 만드는 과정
2. 만들어진 Heap을 가지고 정렬하는 과정

이번 글에서는 첫 번째 과정인 heap을 만드는 과정에 대해 적겠습니다.

 

입력이 {0, 7, 2, 5, 3, 1, 6}(0은 인덱스 1부터 맞춰 적기 위해 끼워 넣은 의미 없는 값)과 같이 들어왔다고 할 때, heap이 만들어지는 과정을 봅시다.

힙 만들기(Heap Construction)

Heap 정렬을 하기 위해서는 먼저 입력받은 배열을 heap 구조를 따르게 재구성해야 합니다. 오름차순으로 정렬하는 것을 목적으로 한다면 max heap으로 구성해야 합니다. 현재 입력받은 배열의 상황은 아래와 같습니다.

초기 상태

Heap의 구조를 만들어가는 과정은 재귀적으로 표현할 수 있습니다.

1. 자신의 왼쪽 서브 트리를 heap 구조로 재구성
2. 자신의 오른쪽 서브 트리를 heap 구조로 재구성
3. 자기 자신이 루트 노드인 현재 트리를 heap으로 재구성

1번과 2번은 재귀로 들어가는 과정이고 핵심은 3번입니다. 이를 c++ 언어로 간단히 표현하면 아래와 같습니다.

// 이 코드는 과정만 보여주는 코드이기 때문에 실제로는 작동하지 않습니다.
void constructHeap(int root, int key, int numNodes)
{
    // root: root 노드의 인덱스
    // key: 노드의 key값
    // numNodes: 트리에 있는 노드 수
    // input: 사용자가 입력한 배열
    if (root > numNodes) return;
    
    constructHeap(root * 2, input[root * 2], numNodes);
    constructHeap(root * 2 + 1, input[root * 2 + 1], numNodes);
    fixHeap(root, key, numNodes);
}

이 과정을 재귀적으로 들어가지 않고 iterative 하게 표현할 수 있습니다. Heap은 complete binary tree 구조이기 때문에 트리의 마지막 레벨에는 리프 노드들만 있습니다. 리프 노드들에서 fixHeap 함수를 호출하는 건 의미가 없습니다. 따라서 트리의 마지막 레벨의 전 레벨에서부터 루트까지 노드 하나씩 iterative 하게 fixHeap을 호출해서 max heap을 만들 수 있습니다.

void constructHeap(int numNodes)
{
    // input: 사용자가 입력으로 준 배열(힙으로 만들어야 할 배열)
    // numNodes: 배열의 원소 수 = 트리에 있는 노드의 수
    for (int i = numNodes / 2; i >= 1; i--)
    { fixHeap(i, input[i], numNodes); }
}

FixHeap

FixHeap 과정을 통해 자기 자신부터 밑의 자식 노드들이 모두 heap 구조를 따르게 만들 수 있습니다. 과정은 아래와 같습니다.

1. 자식 노드들 중 값이 큰 노드를 찾는다.
2. 현재 자신과 값이 큰 자식 노드와 크기 비교를 한다.
3. 만약 자식 노드의 값이 더 크다면 자식 노드의 값을 자기 위치에 덮어쓴다. 그 후로 현재 위치를 값이 큰 자식 위치로 수정한 다음 1번 과정으로 돌아간다.
4. 아니면 현재 위치에 자신의 값을 덮어쓰고 과정을 종료한다.

이 과정을 그림으로 따라가 봅시다. 왼쪽으로 계속 재귀적으로 들어갔다고 가정해봅시다. 그럼 먼저 FixHeap이 진행되는 곳은 이곳입니다.

가장 먼저 fixheap이 일어나는 곳

1번에 따라 자식 노드들 중 큰 값을 찾으면 3이라는 걸 알 수 있습니다. 그다음 3을 2와 비교합니다. 3이 2보다 크기 때문에 3을 2의 위치에 덮어씁니다. 그다음, 현재 자신의 위치를 왼쪽 자식 노드로 설정하고 과정을 반복합니다. 하지만 이제 리프 노드이므로 과정은 끝나게 됩니다.

결과적으로 2와 3의 위치가 바뀌었다.

그 다음 fixheap이 일어나는 곳은 5번 노드가 루트 노드가 되는 오른쪽 서브 트리입니다. 여기에서도 같은 과정에 의해 5와 6의 위치가 바뀝니다.

6과 5의 위치가 바뀌었다.

그리고 다음이자 마지막으로 7번 노드가 루트 노드인 트리에서 fixheap이 일어납니다.

자식 노드들 중에서 큰 값은 6이지만 현재 노드의 값인 7보다 작기 때문에 값의 변화는 일어나지 않은 채 과정이 종료됩니다. 이렇게 maxheap 구조를 완성시킬 수 있게 됩니다.

완성된 MaxHeap

이를 배열로 표현하면 {0, 7, 3, 6, 2, 1, 5}입니다. 지금까지의 과정을 c++ 코드로 표현하면 아래와 같습니다.

void fixHeap(int idx, int key, int numNodes)
{
    // input: 우리가 heap 구조로 만들어야할 배열
    // idx: 현재 노드의 인덱스
    // key: 현재 노드의 값
    // numNodes: 트리에 있는 노드들의 갯수
    while(idx * 2 <= numNodes || idx * 2 + 1 <= numNodes)    // 자식 노드가 하나라도 존재한다면
    {
        int largerChildIdx;    // 자식 노드 중 큰 값을 가진 노드의 인덱스 저장하는 변수
        if (idx * 2 + 1 <= numNodes)    // 만약 오른쪽 서브트리가 존재한다면
        {
            if (input[idx * 2] > input[idx * 2 + 1])    // 왼쪽 자식 값 > 오른쪽 자식 값
            { largerChildIdx = idx * 2; }
            else { largerChildIdx = idx * 2 + 1; }
        }
        else { largerChildIdx = idx * 2; }    // 없으면 무조건 왼쪽 서브트리
        
        if (key < input[largerChildIdx])    // 현재 자신의 값 < 자식 노드 중 큰 값
        {
            input[idx] = input[largerChildIdx];    // 큰 값을 현재 위치에 덮어쓰기
            idx = largerChildIdx;                  // 현재 위치를 큰 값 가졌던 자식 노드로
        }
        else break;    // 아니면 종료
    }
    input[idx] = key;    // 현재 위치에 key값 덮어쓰기
}

FixHeap에서의 Time Complexity

노드 간의 크기 비교하는 연산을 base operation이라고 하고, 트리에 있는 노드의 개수를 N이라고 할 때, fixHeap에서의 time complexity는 O(logN)이라고 할 수 있습니다. 트리를 타고 내려갈 때마다 왼쪽 아님 오른쪽을 선택해서 내려가고 한 번의 while 문에서 최대 2번의 비교(자식 노드가 1개만 있다면 자동적으로 선택되기 때문)가 발생하기 때문에 2 * \( \lfloor \log_{2} N \rfloor \) 이고, big-O 표기법에 의해 O(logN)이 됩니다.

ConstructHeap의 Time Complexity

결론부터 얘기하면 heap을 구성할 때의 시간 복잡도는 O(N)입니다. 이를 얘기하기 위해 지금부터 수식이 많이 나옵니다. 천천히 따라가 봅시다. 설명은 아래의 사이트에서 가져왔습니다.

https://developerhan.tistory.com/32

선형 시간에 힙 만들기 Building Heap in Linear Time

먼저 트리의 높이를 h, 트리의 레벨을 d, 전체 노드의 개수를 N이라고 합시다. 그리고 다음과 같은 complete binary tree가 있다고 합시다.

h = 3인 이진 트리

레벨 0에서 fixHeap이 호출된다면 노드의 키 값이 최대 3번(3 - 0)을 타고 내려갈 수 있습니다.

레벨 1에서 fixHeap이 호출된다면 노드의 키 값이 최대 2번(3 - 1)을 타고 내려갈 수 있습니다.

레벨 2에서 fixHeap이 호출된다면 노드의 키 값이 최대 1번(3 - 2)을 타고 내려갈 수 있습니다.

레벨 3에서는 리프 노드만 있으므로 fixHeap 과정이 일어나지 않습니다.

레벨 d에서의 노드 개수는 \(2^d\) 개입니다. 따라서 일반적인 complete binary tree를 생각할 때, 이 횟수들을 모두 합치면 아래와 같은 수식으로 표현할 수 있습니다.

$$ \sum_{d=0}^{h-1} 2^d \left( h - d \right) $$

이 식을 풀어봅시다.

$$ S = 2^0 \left( h - 0 \right) + 2^1 \left( h - 1 \right) + 2^2 \left( h - 2 \right) + ... + 2^{h-2} \left( 2 \right) + 2^{h-1} \left( 1 \right) $$

이 식을 계산하기 위해 약간의 트릭을 사용하겠습니다. S 값에 2를 곱하고 이 값에 S를 빼겠습니다.(S = 2S - S)

$$ 2S = 2^1 \left( h - 0 \right) + 2^2 \left( h - 1 \right) + 2^3 \left( h - 2 \right) + ... + 2^{h-1} \left( 2 \right) + 2^h \left( 1 \right) $$

$$ 2S - S = -2^0 \left( h - 0 \right) + 2^1 \left( \left( h - 0 \right) - \left( h - 1 \right) \right) + 2^2 \left( \left( h - 1 \right) - \left( h - 2 \right) \right) + ... + 2^h \left( h - \left( h - 1 \right) \right) $$

$$ S = -h + 2^1 + 2^2 + ... + 2^{h-1} + 2^h = -h + 2 \left( 2^h - 1 \right) = 2^{h+1} - h - 2$$

여기서 h는 \( \lfloor log_{2} N \rfloor \)와 같으므로

$$ 2^{h+1} - h - 2 = 2^{log_{2} N + 1} - log_{2} N - 2 = 2N - log_{2} N - 2 $$

Big-O notation에 따라 O(N)이 됩니다.