[C] 우선순위 큐와 힙 (priority queue / heap), 힙 정렬 (Heapsort)

우선수위 큐(priority queue)

 

우선순위 큐는 평범한 큐나 스택과 비슷한 축약 자료형이다

단, 가장 먼저 혹은 나중에 입력된 자료가 가장 먼저 꺼내지는 것이 아니라,

우선순위가 가장 높은 자료가 가장 먼저 꺼내진다

 

이를 균형 잡힌 이진 검색 트리를 사용하면,

(우선순위가) 최대인 원소를 찾아 삭제하는 일과 새 원소를 삽입하는 일 모두 O(logN) 시간에 할 수 있다

 

하지만 이보다 훨씬 단순한 구조로 구현할 수 있는데,

그 중 대표적인 것이 힙(heap)이라는 트리이다

 

---

 

힙(heap)

 

힙은 다음 규칙이 만족하도록 구성된 이진 트리이다 (이진 힙; binary heap)

 

- 마지막 레벨(리프 노드)을 제외한 모든 레벡에 노드가 꽉 차 있어야 한다

- 마지막 레벨에 노드가 있을 때는 항상 가장 왼쪽부터 순서대로 채워져 있어야 한다

최대 힙의 예 (위키백과)

위와 같은 규칙으로 인해 트리의 루트에 가장 큰 원소가 있음을 알 수 있다

이는 최대 힙일 경우이고, 최소 힙도 간단히 바꿔 구현할 수 있습니다

더불어 노드의 개수만으로 트리의 모양이 정해지고, 힙의 높이 역시 O(logN)이라는 사실도 알 수 있다

원소의 삽입/삭제 모두 O(logN)의 시간 복잡도를 가진다

 

이렇게 엄격한 모양 규칙을 이용하여 다음과 같이 배열 하나로 전체 트리를 표현한다

 

- A[i]에 대응되는 노드의 왼쪽 자손은 A[2*i + 1]에 대응된다

- A[i]에 대응되는 노드의 오른쪽 자손은 A[2*i + 2]에 대응된다

- A[i]에 대응되는 노드의 부모는 A[(i-1) / 2]에 대응된다

 

---

 

원소 삽입

 

int *heap;
int idx = 0;

void push_heap(int newValue)
{
    heap[idx++] = newValue; // 맨 끝에 저장

    int i = idx - 1; // 마지막 원소 idx

    while(i > 0 && heap[i] > heap[(i-1) / 2])
    {
        swap(heap + i, heap + ((i-1) / 2));
        i = (i-1) / 2;
    }
}

 

코드에서와 같이 맨 끝 idx에 저장하고,

부모 노드와의 비교를 통해 계속 올라오는 방식이다

 

while문의 내부가 한 번 수행될 때마다 트리에서 한 레벨 위로 올라가게 되므로,

시간 복잡도는 트리의 높이인 O(logN)이 된다

 

---

 

원소 삭제

 

int *heap;
int idx = 0;

void pop_heap()
{
    if(idx == 0)
        return;
        
    heap[0] = heap[--idx]; // 맨 끝 값 루트에 덮어씌우기

    int here = 0;
    while(1)
    {
        int left = here*2 + 1, right = here*2 + 2;

        if(left >= idx) break;

        int next = here;
        if(heap[next] < heap[left]) // 왼쪽 자식 노드 비교
            next = left;
        if(right < idx && heap[next] < heap[right]) // 큰 값과 오른쪽 자식 노드 비교
            next = right;
        
        if(next == here) break;
        swap(heap + here, heap + next);
        here = next;
    }
}

 

이는 트리의 루트 노드를 삭제하는 알고리즘이다

원소 추가 때와는 반대로 맨 끝 원소를 루트 노드에 덮어씌운 후에 자식 노드와 비교하며 계속 내려가는 방식이다

코드와 같이 왼쪽 노드와 오른쪽 노드 더 큰 값과 swap하며 내려가는 것을 알 수 있다

 

이 역시 원소 추가 때와 같이 O(logN)의 시간 복잡도를 가진다

 

---

 

힙 정렬(Heapsort)

 

힙에서 원소들을 꺼낼 때 항상 정렬된 순서대로 반환된다는 점을 이용해보자

 

주어진 배열을 힙으로 만든 뒤 모든 원소들을 꺼내서 반환 순서대로 배열하면 정렬 결과가 된다

 

이 때 힙에서 원소를 하나 꺼내면 힙을 담은 배열의 맨 뒤쪽에 한 칸이 비게 되므로,

최대 원소를 여기에 옮기면 추가 메모리를 사용하지 않고 정렬을 구현할 수 있다

 

이는 합병 정렬(Merge Sort)과는 달리 추가적인 메모리를 요구하지 않으면서,

최악의 경우에도 O(NlogN) 시간 복잡도만을 요구한다