힙(Heap)

2016년 06월 01일 | Jeremy

힙은 특정한 규칙을 만족하도록 구성된 이진 트리로, 단순히 최대 원소를 가능한 한 빠르게 찾을 수 있는 방법으로 설계되었기 때문에 더 단순한 알고리즘으로도 효율적으로 동작할 수 있습니다.

힙이 갖는 가장 중요한 규칙은 부모 노드가 가진 원소는 항상 자식 노드가 가진 원소 이상이라는 것입니다. 이것을 힙의 대호 관계 규칙이라고 부릅니다. 힙에서 대소 관계 규칙은 이진 탐색 트리와 달리 부모 자식 관계에만 적용되며, 왼쪽 자식과 오른쪽 자식이 갖는 원소의 크기는 제한하지 않는다 는 데 유의합시다. 이 규칙에 의하면 트리에서 가장 큰 원소는 항상 트리의 루트에 들어가므로, 최대 원소를 빨리 찾기를 원하는 힙의 목적에 잘 부합합니다.

물론 대소 관계 규칙만으로는 이진 탐색 트리에서도 문제가 되었던, 트리가 한쪽으로 기울어지는 일을 막을 수 없습니다. 힙은 트리의 높이를 항상 일정하게 유지하기 위해 트리의 구조에 제약을 둡니다. 이것은 균형 잡힌 이진 탐색 트리가 트리의 구조를 제약해 속도를 더 빠르게 하는 것과 같지요.

힙의 모양 규칙은 다음과 같은 두 가지의 조건으로 이루어집니다.

마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다.
마지막 레벨에 노드가 있을 때는 항상 가장 왼쪽부터 순서대로 채워져 있어야 한다.

배열을 이용한 힙의 구현

힙이 요구하는 굉장히 엄격한 모양 규칙은 구현할 때는 장점으로 작용합니다. 트리에 포함된 노드의 개수만 알면 트리 전체의 구조를 알 수 있기 때문입니다.

A[i]에 대응되는 노드의 왼쪽 자손은 A[2*i+1]에 대응됩니다.
A[i]에 대응되는 노드의 오른쪽 자손은 A[2*i+2]에 대응됩니다.
A[i]에 대응되는 노드의 부모는 A[(i-1)/2]에 대응됩니다.

새 원소의 삽입

이진 탐색 트리에서는 원소가 들어가야 할 서브트리가 대소 관계 규칙 에 따라 정해지지만, 힙에서는 모양 규칙 이 어느 서브트리로 들어가야 할지를 결정해 줍니다. 트리의 크기가 증가했을 때 새로 생겨나야 할 노드의 위치가 모양 규칙에 의해 결정되기 때문입니다.

모양 규칙에 의해 새 노드는 항상 heap[]의 맨 끝에 추가 됩니다. 힙의 대소 관계 속성은 일단 무시하고, 이 위치에 새 노드를 추가해서 모양 규칙을 만족시킵니다. 그리고 나면 힙의 대소 관계 속성을 만족시키기는 의외로 간단합니다. 마지막에 추가한 새 원소를 자신의 부모 노드가 가진 원소와 비교하고, 부모 노드가 가진 원소가 작다면 두 원소의 위치를 바꿉니다. 새 원소가 더 크거나 같은 원소를 가진 부모 노드를 만나거나, 루트에 도달할 때까지 반복하면 되지요.

// 정수를 담는 최대 힙heap에 새 원소 newValue를 삽입한다.
void push_heap(vector<int>& heap, int newValue) {
    // 힙의 맨 끝에 newValue를 삽입한다.
    heap.push_back(newValue);

    // 현재 newValue의 위치
    int idx = heap.size() - 1;
    // 루트에 도달하거나 newValue 이상의 원소를 가진 조상을 만날 때까지
    while (idx > 0 && heap[(idx - 1) / 2] < heap[idx]) {
        swap(heap[idx], heap[(idx - 1) / 2]);
        idx = (idx - 1) / 2;
    }
}

최대 원소 꺼내기

힙의 모양 구조에 의하면 힙의 마지막에 있는 노드는 어차피 지워질 운명이니, 이 노드를 일단 지우고 시작합시다. 힙의 대소 관계 조건을 만족시키려면 원래 루트의 두 자식이 가지고 있던 원소 중 큰 쪽이 루트에 올라와야 하지요. 따라서 두 자식 노드가 가진 원소 중 더 큰 원소를 선택해 루트가 갖고 있는 원소와 맞바꿉니다. 그리고 이 작업을 트리의 바닥에 도달하거나, 두 자손이 모두 자기 자신 이하의 원소를 갖고 있을 때까지 반복하면 됩니다.

따라서, 힙에서 최대 원소를 꺼내는 핵심은 마지막 노드에 있던 원소로 루트에 있던 원소를 덮어 씌우고, 두 자식 중 더 큰 원소를 가진 노드와 원소를 교환하는 것을 반복 하는 것 입니다.

// 정수를 담는 최대 힙heap에서 heap[0]을 제거한다.
void pop_heap(vector<int>& heap) {
    // 힙의 맨 끝에서 값을 가져와 루트에 덮어씌운다.
    heap[0] = heap.back();
    heap.pop_back();

    int here = 0;
    while (true) {
        int left = here * 2 + 1, right = here * 2 + 2;
        // 리프에 도달한 경우
        if (left >= heap.size()) break;
        // heap[here]가 내려갈 위치를 찾는다.
        int next = here;
        if (heap[next] < heap[left])
            next = left;
        if (right < heap.size() && heap[next] < heap[right])
            next = right;
        if (next == here) break;
        swap(heap[here], heap[next]);
        here = next;
    }
}