09. 자료구조론 - Heap (Priority Queue)

Heap (Priority Queue)

힙 또는 우선순위 큐는 요소가 지워질 때 먼저 들어온 것이 먼저 나가는 것이 아니라 우선순위가 높은 요소가 더 먼저 나가는 자료구조입니다. 

따라서 heap에서는 insert와 pop 연산을 지원하는데, 여기서 pop은 deleteMin이나 deleteMax같은 연산이 됩니다 .

우선순위 큐는 주로 스케줄링을 할 때 사용됩니다.

Heap에는 min heap과 max heap이 있으며 둘의 차이는 다음과 같습니다.

• min heap : 각 부모노드의 값은 자식 노드의 값들보다 항상 작거나 같다. (작은 값이 우선순위가 높을 때 사용)
• max heap : 각 부모노드의 값은 자식 노드의 값들보다 항상 크거나 같다. (큰 값이 우선순위가 높을 때 사용)

따라서 루트노드는 min heap에서 가장 작은 값을 갖고, max heap에서는 가장 큰 값을 갖습니다.

 

그리고 heap은 complete binary tree라는 특징을 갖습니다. 

complete binary tree는 아래의 게시글에 나와있습니다. 쉽게 말해서 노드들을 위에서부터 꽉 채우고 맨 마지막 줄에서는 왼쪽부터 꽉 채운 트리입니다.

05. 자료구조론 - 트리 (Tree)

아래와 같은 것이 min heap입니다.

Min Heap

그리고 트리 게시물에서 작성했듯이 이진트리는 배열을 이용해서 구현할 수 있습니다.

그런데 이진트리에 노드가 듬성듬성하게 들어간 height만 높은 트리라면 배열을 사용했을 때 비는 부분이 많아져 비효율적입니다.

하지만 binary heap은 complete binary tree이기 때문에 배열을 가장 효율적으로 사용할 수 있습니다. 

이진트리를 배열을 사용하여 나타내면 인덱스 i번째 노드에 대해서 자식과 부모 노드의 인덱스를 다음과 같이 구할 수 있습니다.

• 왼쪽 자식노드의 인덱스 : $2i  (2i \leq n)$
• 오른쪽 자식노드의 인덱스 : $2i+1  (2i+1 \leq n)$
• 부모노드의 인덱스 : $\lfloor {i\over 2} \rfloor (i \geq 2)$

위의 Min heap을 배열에 나타내면 다음과 같이 나타낼 수 있습니다.

index	1	2	3	4	5	6	7	8	9	10
노드 값	3	9	4	21	10	13	11	23	30	14

구현

Min heap의 구현에 대해 살펴보겠습니다. Max heap의 구현도 min heap과 비슷하게 구현 가능합니다.

typedef struct _Heap {
    int capacity; // 힙의 최대 사이즈
    int size; // 현재 힙 사이즈
    int *elements;
} Heap;

Insert

Heap에 새로운 값이 insert되면 min heap의 조건이 깨지지 않도록 해당 값을 알맞은 위치로 옮겨주는 작업이 필요합니다. 

그 방법은 다음과 같습니다.

1. 우선 새로운 값을 트리의 맨 마지막에 삽입한다. 

2. 부모의 값과 해당 값을 비교하여 새로운 값이 더 작으면 부모와 위치를 바꾼다.

3. 부모의 값이 더 작아질 때까지 2번 과정을 반복한다. 

위의 과정을 따라 위의 Min heap에 5를 삽입하는 과정은 다음과 같습니다.

void Insert(Heap heap, int x) {
    if (heap->size == heap->capacity) {
        // do something for full heap exception handling
        return;
    }
    int i;
    for (i = ++h->size; h->elements[i/2] > x; i /= 2) {
        h->elements[i] = h->elements[i/2];
    }
    h->elements[i] = x;
}

새로운 값이 부모의 값보다 커질 때까지 부모의 값을 내리는 작업은 최대 트리의 height만큼만 일어나고, heap은 complete binary tree이기 때문에 Insert 연산의 시간복잡도는 $O(log n)$이 됩니다. (자세한 증명은 앞선 게시물의 '이진탐색트리' 참고)

Delete (DeleteMin)

Min heap에서의 삭제연산은 heap 내에서 가장 작은 값을 갖는 요소를 제거하며 리턴하는 연산입니다.

Min heap에서 가장 작은 값은 루트노드에 들어있습니다.

따라서 가장 작은 값을 찾는 것은 $O(1)$ 시간만에 수행할 수 있지만, 중요한 것은 삭제한 이후 다시 heap을 올바르게 정렬해야한다는 것입니다. 

 

바로 생각해볼 수 있는 방법은 루트노드부터 시작해서 자식노드 중 더 작은 것을 한칸씩 위로 올리는 방법입니다. 

하지만 이렇게 하다보면 다음과 같이 맨 마지막 노드를 옮기는데에서 문제가 생길 수 있습니다.

따라서 빈칸을 채울 노드를 결정하는 데에는 다음의 세 노드를 고려해야합니다.

1. 빈 노드의 왼쪽 자식노드

2. 빈 노드의 오른쪽 자식노드

3. 트리의 마지막 노드 (맨 아랫줄의 맨 오른쪽 노드)

이 세 노드 중 가장 값이 작은 노드를 위로 올리면 됩니다.

int DeleteMin(Heap h) {
    int i, child;
    int min_elem, last_elem;

    min_elem = h->elements[1];
    last_elem = h->elements[h->size--];

    for (i = 1; i * 2 <= h->size; i = child) {
        child = i*2;
        if (child < h->size && h->elements[child+1] < h->elements[child]) {
            child++;
        }
        if (last_elem > h->elements[child]) {
            h->elements[i] = h->elements[child]
        } else {
            break;
        }
    }
    h->elements[i] = last_elem;
    return min_elem;
}

Delete의 경우에도 빈칸으로 가장 작은 값을 올리는 행위가 최대 트리의 height만큼만 일어나므로 시간복잡도는 $O(log n)$이 됩니다.

BuildHeap

n개의 노드를 갖는 힙을 생성하는 작업은 시간복잡도가 어떻게 될까요?

한번의 insert에 드는 시간복잡도가 $O(log n)$ 이므로 n번의 insert로 n개짜리 힙을 만들면 $O(nlog n)$이 됩니다.

하지만 만약 정렬되지 않은 상태로 노드들이 이미 배열에 들어가 있다면 그것을 힙의 조건에 맞도록 정렬하는데에는 $O(n)$ 만큼의 시간복잡도가 듭니다. 이를 위해서는 아래의 방법을 사용합니다.

percolating-down은 특정 노드의 자식에 자신보다 작은 값이 없을 때까지 자식노드와 자리를 바꿔가며 계속 내려주는 방식입니다. 

이 과정을 가장 아래에 있는 non-leaf노드부터 시작해서 루트노드까지 차례차례 수행해주면 정렬되지 않았던 배열이 힙으로 정렬됩니다.

증명

0 레벨에는 한 개의 노드가 있고, 이것은 최대 h 레벨까지 내려간다.
1 레벨에는 두 개의 노드가 있고, 이것은 최대 h-1 레벨까지 내려간다.
2 레벨에는 세 개의 노드가 있고, 이것은 최대 h-2 레벨까지 내려간다. 
...
이것을 모두 더한 것을 S라고하면,
$$ S = h + 2(h-1) + 4(h-2) + ... + 2^{h-1}(1)\\
2S = 2h + 4(h-1) + 8(h-2) + ... + 2^{h-1}(2) + 2^{h}(1)\\
2S - S = -h + (2 + 4 + ... + 2^{h-1}) + 2^h\\
= -h - 1 + (1 + 2 + 4 + ... + 2^{h-1}) + 2^h\\
= 2^{h} + 2^{h} - h - 2 = 2*2^{h} - h - 2\\
= 2*2^{log n} - log n - 2 \leq 2*2^{log n} = 2n$$

Heap sort

힙을 이용해 정렬을 구현할 수 있습니다. 방법은 아래와 같습니다.

1. n개의 요소를 이용해 binary heap을 생성한다. ($O(n)$)

2. n번 deleteMin(deleteMax)을 호출해서 리턴된값을 차례차례 저장해둔다. ($O(n log n)$)

따라서 총 시간복잡도는 $O(n log n)$이 됩니다.

 

힙 소트의 단점은 힙 배열을 위한 공간과 정렬된 리스트를 위한 공간을 따로 두어야한다는 것입니다.

이를 해결하기 위해 delete를 하기 직전 힙의 마지막 셀이 delete을 하고 난 후 비게되므로 이 공간을 정렬된 리스트를 저장하기 위한 공간으로 활용할 수 있습니다. (이 경우에는 반대로 오름차순으로 정렬할 경우 max heap을, 내림차순으로 정렬할 경우 min heap을 사용해야 합니다.)

 

/* Max Heap */
void HeapSort(int a[], int n) {
	/* Build Heap */ 
    for (int i = n / 2; i > 0; i--) { 
        PercDown(a, i, n);
    }
    for (int i = n; i > 0; i--) {
    	/* DeleteMax */
        int tmp = a[1];
        a[1] = a[i];
        a[i] = tmp;
        /* 바뀐 루트노드를 올바른 위치로 다시 정렬 */
        PercDown(a, 1, i - 1);
    }
}

void PercDown(int a[], int node, int n) {
	int child;
	for (int i = node; i*2 <= n; i = child) {
    	child = i*2;
        if (child < n && a[child+1] > a[child]) child++;
        
        if (a[i] > a[child]) break;
        else a[i] = a[child];
    }
}