[Computer Terms] 힙과 우선순위 큐 (Heap, Priority Queue)

이 장을 읽기 전에

배열과 연결리스트의 배열 인덱스 계산, 트리의 완전 이진 트리·부모-자식 개념, 그래프까지 이어진 자료구조 기초를 안다고 가정한다. 힙은 트리를 배열 하나로 압축해 표현하는 자료구조이므로, “트리인데 왜 배열로 저장하는가"라는 질문에서 출발한다.

“가장 급한 일부터” 처리하려면

작업 스케줄러가 우선순위가 높은 작업부터 실행하거나, 다익스트라 알고리즘이 현재까지 거리가 가장 짧은 정점부터 확정하는 상황을 생각해보자. 매번 “지금까지 넣은 원소 중 최솟값(또는 최댓값)을 꺼내는” 연산이 반복된다. 정렬된 배열을 쓰면 최솟값 조회는 O(1)이지만 새 원소를 삽입할 때 제자리를 찾아 뒤 원소를 밀어야 해 O(n)이 든다. 균형 이진 탐색 트리를 쓰면 삽입·삭제는 O(log n)이지만 포인터 3개(왼쪽·오른쪽·부모)를 매 노드마다 유지해야 하고 구현이 복잡하다. **힙(Heap)**은 “최솟값 조회"라는 한 가지 연산만 빠르게 지원하는 대신, 트리를 배열 하나로 표현해 구현을 단순화한 절충안이다.

힙의 정의: 완전 이진 트리 + 힙 속성

힙은 두 가지 규칙을 만족하는 이진 트리다. 첫째, 완전 이진 트리(Complete Binary Tree) 규칙 — 마지막 레벨을 제외한 모든 레벨이 꽉 차 있고, 마지막 레벨은 왼쪽부터 채워진다. 둘째, 힙 속성(Heap Property) — 최소 힙(Min-Heap)에서는 모든 부모 노드의 값이 두 자식보다 작거나 같고, 최대 힙(Max-Heap)에서는 그 반대다. 힙 속성은 형제 노드 사이의 크기 관계는 규정하지 않는다는 점에서 BST의 “왼쪽 < 부모 < 오른쪽” 전순서 규칙보다 약하다 — 이 약한 제약 덕분에 삽입·삭제가 국소적인 비교·교환만으로 끝난다.

완전 이진 트리라는 규칙 덕분에 힙은 포인터 없이 배열로 표현할 수 있다. 인덱스 i(0-based)에 저장된 노드의 부모는 (i - 1) / 2, 왼쪽 자식은 2*i + 1, 오른쪽 자식은 2*i + 2에 위치한다. 트리의 “빈틈없이 왼쪽부터 채운다"는 규칙이 배열의 “빈틈없이 인덱스를 채운다"는 성질과 정확히 대응하기 때문에 이 공식이 성립한다. 노드 사이를 오가는 데 포인터 역참조 대신 정수 연산만 쓰므로 캐시 지역성도 연결 기반 트리보다 유리하다.

값 10, 5, 3, 8, 1을 이 순서로 삽입한 최소 힙은 배열 [1, 3, 5, 10, 8]이 되며(뒤에 나올 sift-up 규칙을 그대로 적용한 결과), 트리와 배열 인덱스는 다음과 같이 대응한다.

graph TD
    I0["idx 0: 1"] --> I1["idx 1: 3"]
    I0 --> I2["idx 2: 5"]
    I1 --> I3["idx 3: 10"]
    I1 --> I4["idx 4: 8"]

idx 1(값 3)의 부모는 (1-1)/2 = idx 0, 자식은 2*1+1 = idx 3과 2*1+2 = idx 4로, 배열 인덱스만으로 트리 상의 위치가 그대로 계산됨을 확인할 수 있다.

삽입: sift-up으로 힙 속성 복구

새 원소는 항상 배열의 맨 끝(완전 이진 트리의 다음 빈자리)에 추가한다. 이 위치는 완전 이진 트리 규칙은 지키지만 힙 속성이 깨져 있을 수 있으므로, 새 노드를 부모와 비교해 힙 속성을 어기면 교환하고, 그 자리에서 다시 부모와 비교하는 과정을 반복한다. 이를 sift-up(또는 bubble-up)이라 한다. 트리의 높이가 항상 ⌊log₂ n⌋이므로, 새 노드가 교환을 반복하며 루트까지 올라가는 최악의 경우도 O(log n)번의 비교로 끝난다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <stdio.h>
#include <stdlib.h>

#define MAX_HEAP_SIZE 128

typedef struct {
    int data[MAX_HEAP_SIZE];
    int size;
} MinHeap;

void heap_init(MinHeap *h) {
    h->size = 0;
}

static void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

/* 인덱스 i의 노드를 부모와 비교하며 위로 올린다 : O(log n) */
static void sift_up(MinHeap *h, int i) {
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (h->data[parent] <= h->data[i]) break;
        swap(&h->data[parent], &h->data[i]);
        i = parent;
    }
}

void heap_insert(MinHeap *h, int value) {
    if (h->size >= MAX_HEAP_SIZE) {
        fprintf(stderr, "heap full\n");
        return;
    }
    h->data[h->size] = value;
    sift_up(h, h->size);
    h->size++;
}

int main(void) {
    MinHeap h;
    heap_init(&h);
    int values[] = {5, 3, 8, 1, 9, 2};
    for (size_t i = 0; i < sizeof(values) / sizeof(values[0]); i++) {
        heap_insert(&h, values[i]);
    }

    printf("root (min): %d\n", h.data[0]);   /* 항상 1이 출력됨 */
    printf("heap size: %d\n", h.size);
    return 0;
}

sift_up은 새로 들어온 값이 부모보다 작을 때만 교환하며 위로 이동하고, 부모보다 크거나 같아지는 순간(또는 루트에 도달하면) 멈춘다. 루프가 매 반복마다 인덱스를 부모 위치로 옮기므로 트리 높이만큼만 반복되고, 나머지 노드는 전혀 건드리지 않는다는 점이 O(n) 정렬 삽입과의 핵심 차이다.

삭제: sift-down으로 루트를 재구성

최소 힙에서 꺼낼 값은 항상 루트(인덱스 0)다. 루트를 제거한 뒤 트리 모양을 유지하려면, 배열의 마지막 원소를 루트 자리로 옮기고 크기를 하나 줄인 다음, 이 원소를 자식들과 비교하며 힙 속성이 회복될 때까지 아래로 내린다. 이를 sift-down(또는 sink)이라 한다. 두 자식 중 더 작은 쪽과 비교해 그보다 크면 교환해야 최소 힙 속성이 유지되므로, 매 단계에서 두 자식 중 작은 값을 먼저 찾는다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* 루트에서 시작해 자식과 비교하며 아래로 내린다 : O(log n) */
static void sift_down(MinHeap *h, int i) {
    while (1) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int smallest = i;

        if (left < h->size && h->data[left] < h->data[smallest]) smallest = left;
        if (right < h->size && h->data[right] < h->data[smallest]) smallest = right;
        if (smallest == i) break;

        swap(&h->data[i], &h->data[smallest]);
        i = smallest;
    }
}

int heap_extract_min(MinHeap *h) {
    int min = h->data[0];
    h->size--;
    h->data[0] = h->data[h->size];
    sift_down(h, 0);
    return min;
}

heap_extract_min이 루트를 반환하기 전에 마지막 원소를 루트로 옮기는 것은 “완전 이진 트리 모양을 항상 유지한다"는 힙의 전제를 지키기 위해서다. 임의의 다른 노드를 루트 자리에 옮기면 마지막 레벨에 구멍이 생겨 배열 인덱스 공식(2*i+1, 2*i+2)이 더는 성립하지 않는다.

비교: 정렬된 배열/BST/힙

특성	정렬된 배열	균형 BST	힙
최솟값 조회	O(1)	O(log n)	O(1)
최솟값 삭제	O(n) (이동)	O(log n)	O(log n)
임의 값 삽입	O(n) (이동)	O(log n)	O(log n)
임의 값 탐색	O(log n)	O(log n)	O(n) — 힙 속성만으론 보장 안 됨
정렬된 순서로 전체 순회	O(n)	O(n) (중위 순회)	지원 안 함 (매번 추출해야 함)
구현 복잡도	낮음	높음 (균형 유지 로직)	낮음 (배열 인덱스 연산만)

힙이 “임의 값 탐색"을 지원하지 못하는 이유는 힙 속성이 형제 사이의 순서를 규정하지 않기 때문이다 — 왼쪽 자식과 오른쪽 자식 중 어느 쪽에 특정 값이 있는지 힙 구조만으로는 알 수 없어, BST처럼 한쪽을 가지치기할 수 없다. 이 트레이드오프 덕분에 힙은 “최솟값/최댓값만 반복해서 꺼낸다"는 우선순위 큐 용도에 정확히 맞을 때 균형 BST보다 구현이 단순하면서도 같은 O(log n) 삽입·삭제 성능을 낸다.

이 탐색 불가 성질은 앞서 예로 든 다익스트라 알고리즘에서 실제 문제가 된다. 다익스트라는 정점의 거리가 갱신될 때마다 힙에 이미 들어 있는 그 정점의 우선순위를 낮춰야 하는데(decrease-key), 배열 기반 힙은 “정점 v가 배열의 몇 번 인덱스에 있는가"를 알 방법이 없어 이 갱신 대상을 O(n) 선형 탐색 없이는 찾을 수 없다. 최단 경로 알고리즘의 구현이 이 문제를 우회하는 방법은 두 가지다. 하나는 정점 번호를 배열 인덱스로 매핑하는 별도 표(인덱스 힙, Indexed Priority Queue)를 함께 유지해 O(log n)에 위치를 찾는 것이고, 다른 하나는 갱신할 때마다 기존 항목을 지우지 않고 새 (거리, 정점) 쌍을 그냥 추가로 push한 뒤(Lazy Deletion), pop 시점에 “이미 처리된 정점인지"만 확인해 오래된 항목을 건너뛰는 것이다. 후자가 구현이 단순해 실무에서 더 널리 쓰인다.

흔한 오개념

“힙은 정렬된 자료구조다” — 힙 속성은 부모-자식 관계만 규정할 뿐 형제 사이의 순서는 규정하지 않는다. 왼쪽 자식이 오른쪽 자식보다 클 수도 작을 수도 있으므로, 힙 배열을 그대로 출력해도 오름차순이 되지 않는다. 정렬된 결과가 필요하면 extract_min을 n번 반복해야 하며, 이 과정 자체가 힙 정렬(Heapsort)의 원리다.

“힙에서 아무 값이나 빠르게 찾을 수 있다” — 힙이 O(log n) 삽입·삭제를 지원한다고 해서 임의 값 탐색도 빠르다고 착각하기 쉽다. 힙은 특정 값이 왼쪽 서브트리에 있는지 오른쪽 서브트리에 있는지 판단할 근거(BST의 정렬 규칙 같은)가 없어 최악의 경우 배열 전체를 O(n)으로 훑어야 한다. 특정 값의 존재 여부를 빠르게 확인해야 한다면 힙이 아니라 해시테이블이나 BST를 써야 한다.

다른 개념과의 연결

힙의 배열 기반 인덱스 공식(부모 (i-1)/2, 자식 2i+1/2i+2)은 트리의 포인터 기반 노드 구조를 배열로 압축한 것이며, sift-up·sift-down은 트리 순회의 특수한 형태다. 다음 장에서 다룰 **트라이(Trie)**는 힙과 정반대 방향의 트레이드오프를 보여준다 — 힙이 “값의 순서(최솟값)“에 최적화됐다면, 트라이는 “문자열의 접두사 구조"에 최적화된 트리다.

평가 기준

이 챕터를 읽은 후에는 다음을 할 수 있어야 한다. 힙이 완전 이진 트리를 배열로 표현할 수 있는 이유와 부모/자식 인덱스 공식을 유도할 수 있다. sift-up과 sift-down이 각각 삽입·삭제 상황에서 왜 O(log n)에 끝나는지 트리 높이를 근거로 설명할 수 있다. 최솟값 반복 추출이 필요한 상황에서 정렬된 배열·균형 BST·힙 중 힙을 선택해야 하는 이유를 근거와 함께 제시할 수 있다.