우선순위 큐

수치해석 소프트웨어 마지막 수정: 2026-08-23 04:24:11

1. 개요[편집]

우선순위 큐 Priority Queue
기본 연산	insert · find-min · delete-min
확장 연산	decrease-key · meld(합병) · delete
표준 구현	이진 힙(배열 기반, 암시적 트리)
이론 최적	피보나치 힙 · 브로달 큐
실전 국룰	$d$-항 힙 + 지연 삭제
주 소비처	다익스트라 · A* · 이벤트 스케줄러

자료구조 수업에서는 피보나치 힙이 이기고, 프로파일러 앞에서는 4항 힙이 이긴다.

우선순위 큐(priority queue)는 원소마다 키(우선순위)를 달아 두고 “가장 작은(또는 큰) 키를 가진 원소를 꺼내는” 연산을 지원하는 추상 자료형이다. FIFO 큐가 “먼저 들어온 것”을 꺼낸다면 우선순위 큐는 “가장 급한 것”을 꺼낸다. 인터페이스는 insert, find-min, delete-min 세 개면 최소한이고, 여기에 decrease-key(이미 들어 있는 원소의 키를 낮추기)와 meld(두 큐 합치기)가 붙느냐 마느냐로 구현 지형이 통째로 갈린다.

수치해석·시뮬레이션 쪽에서 이 자료구조가 중요한 이유는 하나다. “다음에 처리할 것을 값 순서로 고른다”는 패턴이 이 바닥에 널려 있기 때문이다. 다익스트라 알고리즘과 최소 신장 트리의 프림, A* 알고리즘의 오픈 리스트, 고속 행진법의 좁은 띠(narrow band), 하드스피어 분자동역학의 충돌 달력, 희소 촐레스키 분해의 최소차수 선택이 전부 같은 껍데기를 쓴다. 그래서 이 문서들의 복잡도표는 사실 이 문서의 복잡도표다.

2. 이진 힙 — 배열 하나로 끝나는 트리[편집]

표준 구현은 이진 힙(binary heap, Williams 1964)이다. 완전 이진트리를 배열에 담되 노드 $i$ 의 자식을 $2i+1, 2i+2$ 에 두고, 부모의 키가 자식보다 크지 않다는 힙 성질만 유지한다. 포인터가 없으므로 메모리가 배열 하나뿐이고 캐시 지역성이 좋다.

insert: 끝에 붙이고 부모와 비교하며 올린다(sift-up). $O(\log n)$ .
delete-min: 루트를 빼고 마지막 원소를 루트로 옮긴 뒤 내려보낸다(sift-down). $O(\log n)$ .
find-min: 배열 0번. $O(1)$ .
무작위 배열을 한꺼번에 힙으로 만드는 heapify 는 놀랍게도 $O(n)$ 이다. 깊은 노드가 압도적으로 많고 그것들의 sift-down 거리가 짧기 때문.

decrease-key 도 sift-up 한 번이라 $O(\log n)$ 인데, 문제는 “그 원소가 배열 어디 있는지”를 알아야 한다는 것이다. 그래서 정점 번호 → 힙 위치의 역참조 배열을 따로 유지하고 sift 할 때마다 갱신해야 한다. 이 부가 비용이 뒤에 나올 지연 삭제 관용구의 존재 이유다.

$d$ -항 힙은 자식을 $d$ 개로 늘린 변형이다. 높이가 $\log_d n$ 으로 낮아져 decrease-key(올리기)가 싸지는 대신, delete-min(내리기)은 각 층에서 $d$ 개를 비교해야 하니 $O(d\log_d n)$ 으로 비싸진다. decrease-key 가 delete-min 보다 훨씬 많이 일어나는 상황 — 정확히 다익스트라( $E$ 회 대 $V$ 회) — 에서 $d \approx E/V$ 로 잡으면 총 비용이 $O(E\log_{E/V} V)$ 가 된다. 게다가 자식 $d$ 개가 연속된 메모리에 놓여 캐시 라인 하나에 들어오므로, $d = 4$ 나 $8$ 은 이론과 무관하게 그냥 빠르다.¹

3. 상각 복잡도표 — decrease-key 를 얼마에 파느냐[편집]

힙 종류를 가르는 축은 사실상 decrease-key 하나다.

구현	insert	delete-min	decrease-key	meld
정렬 안 된 배열	$O(1)$	$O(n)$	$O(1)$	$O(1)$
이진 힙	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(n)$
$d$ -항 힙	$O(\log_d n)$	$O(d\log_d n)$	$O(\log_d n)$	$O(n)$
이항 힙	$O(1)$ 상각	$O(\log n)$	$O(\log n)$	$O(\log n)$
페어링 힙	$O(1)$	$O(\log n)$ 상각	상각, 아래 각주	$O(1)$
피보나치 힙	$O(1)$	$O(\log n)$ 상각	$O(1)$ 상각	$O(1)$

이항 힙(Vuillemin 1978)은 크기가 $2^k$ 인 이항트리들의 목록으로 힙을 표현한다. 원소 개수의 이진 표현이 곧 트리 목록이라, 두 힙을 합치는 것이 이진 덧셈의 자리올림과 똑같아진다. meld 를 $O(\log n)$ 에 지원하는 최초의 실용적 힙이었다.

피보나치 힙(Fredman·Tarjan 1984)은 여기서 한 발 더 나간다. 게으름이 핵심이다 — insert 는 그냥 루트 목록에 던져 넣고, decrease-key 는 노드를 부모에서 잘라내 루트 목록으로 옮기기만 한다. 정리(트리 합병)는 delete-min 때 몰아서 한다. 여기에 “자식을 두 번 잃은 부모는 자기도 잘려 올라간다”는 캐스케이딩 컷 규칙을 얹으면 트리의 차수가 $O(\log n)$ 으로 묶이고, 퍼텐셜 함수 논증으로 decrease-key 상각 $O(1)$ 이 나온다. 트리 크기의 하계가 피보나치 수열이라서 붙은 이름이다.

페어링 힙(Fredman 외 1986)은 피보나치 힙의 실용판이다. 구현이 훨씬 단순하고 실측 성능도 좋은데, decrease-key 의 정확한 상각 비용이 아직 미해결이다. $O(1)$ 은 아님이 증명됐고(하계 $\Omega(\log\log n)$ ), 알려진 상계는 그보다 살짝 크다.² 최악 시간 보장까지 원하면 브로달 큐(1996)나 엄격 피보나치 힙(2012)이 있는데, 상수와 구현 난이도 때문에 교과서 밖으로 잘 안 나온다.

4. decrease-key 가 왜 점근을 바꾸는가[편집]

다익스트라와 프림의 루프는 구조가 같다. 정점당 delete-min 한 번( $V$ 회), 간선당 decrease-key 한 번( $E$ 회). 그러니 총 비용은

T = V \cdot C_{\text{delete-min}} + E \cdot C_{\text{decrease-key}}

이진 힙이면 $O((V+E)\log V) = O(E\log V)$ , 피보나치 힙이면 $O(V\log V + E\cdot 1) = O(E + V\log V)$ 다. 희소 그래프( $E = O(V)$ )에서는 $\log V$ 배 차이지만, 조밀 그래프에서는 이야기가 다르다. $E = \Theta(V^2)$ 이면 이진 힙이 $O(V^2\log V)$ , 피보나치 힙이 $O(V^2)$ 가 되어 힙 없는 원조 $O(V^2)$ 판과 같아진다. 즉 “피보나치 힙의 승리”는 조밀 그래프에서 배열 선형탐색을 따라잡는 것이고, 희소 그래프에서만 진짜 이득이다.

그런데 실측은 자주 반대로 나온다. 이유는 셋이다. (1) 피보나치 힙의 노드가 포인터 네 개(부모·자식·좌우 형제)와 차수·마크 필드를 들고 다녀 메모리 트래픽이 크다. (2) 루트 목록을 훑는 delete-min 이 캐시를 사방으로 흩뿌린다. (3) 상각 $O(1)$ 의 숨은 상수가 이진 힙 sift-up 의 실제 비용보다 크다. 결론적으로 정점 수백만 이하, 간선 상수 배 규모의 현실적인 그래프에서는 4항 힙이 거의 항상 이긴다. 이론적 최적이 실전에서 지는 대표 사례로 자주 인용된다.

5. 지연 삭제 — 실무의 항복 선언[편집]

decrease-key 를 쓰려면 역참조 배열을 유지해야 하고, C++ std::priority_queue 나 파이썬 heapq 에는 아예 그 연산이 없다. 그래서 실무 구현은 대개 지연 삭제(lazy deletion) 관용구로 도망간다.

거리를 갱신할 때 힙 안의 항목을 고치지 않고 (새 거리, 정점) 을 그냥 하나 더 넣는다.
꺼낼 때 꺼낸 거리 > 현재 확정 거리[정점] 이면 낡은 항목이므로 버리고 다음을 꺼낸다.

힙 크기가 $O(V)$ 에서 $O(E)$ 로 커지지만 $O(E\log E) = O(E\log V)$ 라 점근은 그대로다. 대신 역참조 배열이 사라지고, 힙 노드가 그냥 값 두 개짜리 구조체가 되며, 캐시 동작이 극적으로 좋아진다. 이 관용구가 다익스트라 알고리즘·A* 알고리즘 구현의 사실상 표준인 이유다.

이벤트 스케줄러에서는 같은 트릭을 유효성 도장으로 쓴다. 원소마다 세대 번호를 붙여 두고, 대상이 갱신되면 세대만 올린다. 꺼낸 항목의 세대가 현재 세대와 다르면 폐기. 힙에서 임의 원소를 지우는 비싼 연산을 세대 정수 비교 하나로 바꾸는 것이다.

6. 키가 작은 정수라면 — 버킷과 단조 큐[편집]

비교 기반 힙의 $\log n$ 이 아까운 경우가 있다. 꺼내는 키가 단조 증가하고(다익스트라가 그렇다) 간선 가중치가 $1$ 부터 $C$ 사이 정수라면, 힙 대신 버킷 배열을 쓸 수 있다. 다이얼의 알고리즘은 거리값마다 버킷을 하나 두고 포인터를 앞으로만 굴려 $O(E + VC)$ 를 얻는다. 버킷 수를 $\log$ 규모로 줄인 기수 힙(radix heap)은 $O(E + V\log C)$ 다.

이 발상은 그래프 밖에서도 유용하다. 그래프 색칠의 DSATUR 는 포화도라는 작은 정수를 키로 쓰므로 버킷이 힙보다 빠르고, 뒤에 나올 최소차수 정렬도 차수를 키로 쓰므로 마찬가지다. 키의 값역이 좁으면 비교 기반의 $\log n$ 은 낼 필요 없는 세금이라는 것이 요점이다.

7. 수치 시뮬레이션에서의 쓰임[편집]

이벤트 구동 분자동역학. 하드스피어 계에서는 입자가 충돌과 충돌 사이에 등속 직선운동을 하므로 시간을 잘게 쪼갤 이유가 없다. 대신 다음 충돌 시각을 키로 하는 우선순위 큐(충돌 달력)를 두고 가장 이른 사건으로 시계를 점프시킨다. 충돌이 일어나면 관련된 두 입자가 끼어 있던 예정 사건이 전부 무효가 되는데, 힙에서 그것들을 찾아 지우는 대신 위의 세대 도장으로 처리한다. 앨더와 웨인라이트의 1957년 하드스피어 계산이 이 방식의 원조이며³, 사건 밀도가 균일할 때는 힙 대신 달력 큐(calendar queue, Brown 1988)로 상각 $O(1)$ 을 노린다. 자세한 물리는 이산 사건 시뮬레이션과 분자동역학 쪽 이야기.
희소 촐레스키의 최소차수 정렬. 촐레스키 분해의 충전(fill-in)을 줄이려면 소거 순서를 잘 골라야 하고, 고전적 휴리스틱은 매 단계 소거 그래프에서 차수가 가장 작은 정점을 고르는 것이다. 이 “매번 최솟값 뽑기”가 정확히 우선순위 큐이며, 정점을 소거할 때마다 이웃의 차수가 바뀌므로 키 갱신이 대량으로 발생한다. 차수는 작은 정수라 실제 구현(AMD·MMD)은 차수별 연결 리스트, 즉 버킷을 쓴다. 최소차수 정렬이 희소행렬 직접 솔버의 전처리 단계에서 하는 일이 이것이다.
A* 알고리즘의 오픈 리스트. $f = g + h$ 를 키로 하는 힙이 오픈 리스트다. A*에서는 동점이 대량으로 발생하므로 동점 처리 규칙이 성능을 좌우한다 — 같은 $f$ 면 $g$ 가 큰 쪽을 먼저 꺼내는 것이 국룰이고, 이것만으로 확장 노드 수가 몇 배 줄기도 한다. 즉 키를 $(f, -g)$ 사전식으로 쓰는 셈.
고속 행진법의 좁은 띠. 도달시간이 최소인 격자점을 확정하고 이웃을 갱신하는 루프가 다익스트라와 글자 단위로 같고, 그 갱신이 곧 decrease-key 다. 격자점 수가 $N$ 이면 $O(N\log N)$ 이 나오는 근거가 힙이다.
다중 시간간격 적분. 중력 $N$ 체 계산에서 입자마다 시간간격이 다른 블록 시간간격 방식은 “다음 갱신 시각”을 키로 하는 큐로 관리한다. 별 하나가 근접 조우 중이라 시간간격이 짧아지면 그 입자만 자주 꺼내진다.
정렬 알고리즘과 병합. 힙정렬은 힙 하나로 $O(n\log n)$ 제자리 정렬을 하고, $k$ 개의 정렬된 리스트를 합치는 $k$ -way merge 는 크기 $k$ 짜리 힙으로 한다. 후자는 희소행렬 곱셈·덧셈에서 각 행의 열 인덱스를 병합할 때 그대로 쓰인다.

8. 현업에서의 현실[편집]

라이브러리 힙에 decrease-key 가 없다고 짜증 내지 말자. 십중팔구 지연 삭제 쪽이 더 빠르다.
힙에 넣는 구조체가 커지면 그 순간 힙은 느려진다. 키와 인덱스만 넣고 나머지는 배열에서 찾아라.
“피보나치 힙 써서 최적화했습니다”라고 말하기 전에 벤치마크를 돌려라. 대체로 느려진다.
부동소수 키의 동점 처리를 정의하지 않으면 실행마다 결과가 미묘하게 달라진다. 재현성이 필요한 해석 코드에서는 정점 번호를 마지막 동점 기준으로 넣는 것이 안전하다.

9. 관련 문서[편집]

캐시 라인이 64바이트면 8바이트 키 여덟 개가 한 줄에 들어온다. $d=8$ 짜리 힙의 delete-min 이 각 층에서 하는 비교 여덟 번은 메모리 접근 한 번어치라, 이론상 늘어난 비교 횟수가 실제로는 거의 공짜다. 상수 배 이야기가 점근을 이기는 전형. ↩
Fredman(1999)이 페어링 힙의 decrease-key 상각 비용에 $\Omega(\log\log n)$ 하계를 증명했고, Pettie(2005)가 $O(2^{2\sqrt{\lg\lg n}})$ 상계를 보였다. 둘 사이 간격이 20년째 안 닫힌 상태다. “실무에서 제일 잘 되는데 왜 잘 되는지 모른다”는 자료구조계의 대표적 미결 문제. ↩
Alder, B. J., Wainwright, T. E. (1957). “Phase Transition for a Hard Sphere System”. J. Chem. Phys. 27, 1208. 컴퓨터 시뮬레이션이 통계역학에 실제로 새 사실을 알려 준 최초의 사건 중 하나다(딱딱한 구만으로도 고체-액체 상전이가 일어난다). 그 밑바닥에 깔린 게 우선순위 큐라는 점은 자료구조 수업에서 잘 안 알려 준다. ↩