우선순위 큐

우선순위 큐는 가장 급한 것부터 꺼내 주는 줄입니다. 항목마다 순위를 붙여서 넣습니다. 꺼낼 때는 남은 것 중 순위가 가장 높은 것이 나옵니다. 늦게 들어온 일이라도 급하면 먼저 처리해야 할 때 씁니다.

상세

이 절은 우선순위 큐가 무엇을 약속하는지부터 봅니다. 작업 세 개를 넣고 꺼내는 예로 그 약속을 확인합니다.

그다음 그 약속을 가장 흔히 지키는 방법인 힙을 숫자 일곱 개짜리 그림으로 따라갑니다. 끝으로 어디에 쓰고 언제 안 쓰는지를 봅니다.

순위대로 꺼내는 규칙

우선순위 큐에 넣는 항목은 저마다 우선순위라는 값을 하나씩 가집니다. 우선순위는 이 항목을 얼마나 먼저 꺼내야 하는지를 나타내는 값입니다. 꺼낼 때는 들어온 순서를 보지 않고 이 값만 봅니다.

작업 세 개를 차례로 넣는다고 해 봅시다. 숫자가 작을수록 급하다고 정합니다.

결제 확인은 두 번째로 들어왔지만 가장 먼저 나옵니다. 메일 발송은 가장 먼저 들어왔지만 가장 늦게 나옵니다. 넣은 순서와 꺼내는 순서가 이렇게 다릅니다.

숫자가 작은 쪽을 먼저 꺼내는 것을 최소 우선순위 큐라고 부릅니다. 큰 쪽을 먼저 꺼내는 것은 최대 우선순위 큐입니다. 둘은 비교 방향만 반대입니다. 동작은 같습니다. 이 문서는 작은 숫자가 급한 쪽으로 씁니다.

이름에 큐가 붙었지만 큐와는 꺼내는 규칙이 다릅니다. 큐는 먼저 들어온 것을 먼저 꺼냅니다. 우선순위 큐는 그 규칙을 「순위가 높은 것을 먼저」로 바꾼 것입니다.

약속하는 동작 셋

우선순위 큐가 약속하는 동작은 셋입니다.

이 표는 각 동작이 무엇을 하는지만 정합니다. 안에서 항목을 어떻게 담는지는 정하지 않습니다. 이렇게 동작만 정해 둔 자료형을 추상 자료형이라고 부릅니다.

그래서 우선순위 큐는 여러 방법으로 만들 수 있습니다. 방법마다 동작에 드는 시간이 다릅니다. 다음 소절이 그 차이를 봅니다.

만드는 방법에 따라 갈리는 시간

동작에 드는 시간은 빅오 표기법으로 적습니다. 항목이 n 개일 때 시간이 n 을 따라 어떻게 늘어나는지만 보는 표기입니다. O(1) 은 항목 수와 상관없이 일정합니다. O(n) 은 항목 수에 비례해 늘어납니다. O(log n) 은 항목 수가 두 배가 될 때마다 한 단계씩만 늡니다.

가장 먼저 떠오르는 방법은 배열에 그냥 담는 것입니다. 넣을 때는 끝에 붙이면 끝나서 O(1) 입니다. 대신 꺼낼 때마다 가장 급한 것을 찾으려고 배열 전체를 훑어야 해서 O(n) 이 듭니다.

반대로 배열을 늘 순위대로 정렬해 두는 방법이 있습니다. 가장 급한 것이 한쪽 끝에 있으니 꺼내기는 O(1) 입니다. 대신 넣을 때마다 제자리를 찾아 뒤의 항목을 한 칸씩 밀어야 해서 O(n) 이 듭니다.

배열 두 방법은 한쪽 동작을 싸게 만드는 대신 다른 쪽이 항목 수에 비례해 늘어납니다. 이진 힙은 넣기와 꺼내기를 둘 다 O(log n) 에 맞춥니다. 그래서 넣기와 꺼내기가 섞여 계속 일어나는 일에는 힙을 씁니다.

힙이라는 모양

힙은 항목을 트리 모양으로 담습니다. 트리는 항목을 위에서 아래로 가지 치듯 매달아 두는 구조입니다. 트리에서 항목 하나하나를 노드라고 부릅니다.

한 노드 바로 아래에 매달린 노드를 자식이라고 부릅니다. 반대로 바로 위의 노드는 부모입니다. 맨 위에 있어 부모가 없는 노드는 뿌리입니다.

힙이 지키는 규칙은 하나입니다. 부모는 언제나 자식보다 급합니다. 이 규칙 덕분에 가장 급한 항목은 늘 뿌리에 있습니다. 들여다보기가 O(1) 에 끝나는 까닭입니다.

자료구조의 힙은 프로그램이 메모리를 빌려 쓰는 영역인 힙과 이름만 같습니다. 이 문서의 힙은 언제나 자료구조 쪽입니다.

흔히 쓰는 것은 한 노드가 자식을 둘까지 두는 이진 힙입니다. 아래는 항목 일곱 개가 든 이진 힙입니다. 노드의 숫자는 우선순위입니다.

flowchart TD
    A["2"] --> B["4"]
    A --> C["3"]
    B --> D["8"]
    B --> E["5"]
    C --> F["6"]
    C --> G["9"]

모든 부모가 자식보다 작습니다. 반면 같은 부모를 둔 두 자식끼리는 순서가 없습니다. 왼쪽의 4 가 오른쪽의 3 보다 커도 규칙에 어긋나지 않습니다.

힙은 항목 전부를 정렬해 두지 않습니다. 부모와 자식 사이만 맞춰 둡니다. 맞출 것이 적어서 넣고 꺼낼 때 손볼 곳도 적습니다.

배열 하나에 담는 트리

이진 힙은 완전 이진 트리 모양을 지킵니다. 위층부터 채우는 트리라는 뜻입니다. 한 층 안에서는 왼쪽부터 빈틈없이 채웁니다. 이렇게 빈틈이 없어야 트리를 배열 하나에 빈칸 없이 담을 수 있습니다.

이진 힙은 노드끼리 포인터로 잇지 않고 배열 하나에 담습니다. 뿌리를 0번 칸에 둡니다. 그 아래로는 층마다 왼쪽부터 차례로 칸을 채웁니다. 위 그림에 칸 번호를 붙이면 아래와 같습니다.

flowchart TD
    A["2 · 0번 칸"] --> B["4 · 1번 칸"]
    A --> C["3 · 2번 칸"]
    B --> D["8 · 3번 칸"]
    B --> E["5 · 4번 칸"]
    C --> F["6 · 5번 칸"]
    C --> G["9 · 6번 칸"]

노드마다 앞 숫자는 우선순위입니다. 뒤는 그 항목이 든 칸 번호입니다. 칸 번호 순서대로 늘어놓으면 배열은 [2, 4, 3, 8, 5, 6, 9] 입니다.

이렇게 담으면 칸 번호 계산만으로 부모와 자식을 오갈 수 있습니다. i 번 칸의 자식은 2i+1 번과 2i+2 번 칸에 있습니다. 1번 칸의 4 는 자식으로 3번 칸의 8 과 4번 칸의 5 를 둡니다.

거꾸로 부모는 (i−1)÷2 번 칸입니다. 나눗셈의 나머지는 버립니다. 4번 칸의 5 는 (4−1)÷2 가 1 이라서 1번 칸의 4 가 부모입니다.

완전 이진 트리는 한 층 내려갈 때마다 칸 수가 두 배로 늡니다. 그래서 항목이 n 개면 층 수는 log₂ n 안팎입니다. 항목이 백만 개여도 스무 층쯤입니다.

넣을 때 올라가는 길

새 항목은 먼저 배열 맨 끝에 붙습니다. 트리로 보면 가장 아래층의 첫 빈칸입니다. 모양은 이것으로 지켜지지만 부모가 자식보다 급하다는 규칙이 깨질 수 있습니다.

그래서 새 항목을 부모와 견줍니다. 새 항목이 더 급하면 둘을 맞바꾸고 한 층 올라가 다시 견줍니다. 부모가 더 급하거나 뿌리에 닿으면 멈춥니다.

위 힙에 우선순위 1 을 넣어 봅시다. 1 은 먼저 맨 끝인 7번 칸에 붙습니다. 트리로 보면 8 의 자식입니다.

flowchart TD
    A["2"] -->|"③ 2 와 맞바꿈"| B["4"]
    A --> C["3"]
    B -->|"② 4 와 맞바꿈"| D["8"]
    B --> E["5"]
    C --> F["6"]
    C --> G["9"]
    D -->|"① 8 과 맞바꿈"| H["1"]

1 이 8 보다 작으니 둘을 맞바꿉니다. 이어서 4 와, 그다음 2 와 맞바꿉니다. 그림에 적은 번호가 이 순서입니다. 세 번 맞바꾸고 뿌리에 닿아 멈춘 모양이 아래입니다.

flowchart TD
    A["1"] --> B["2"]
    A --> C["3"]
    B --> D["4"]
    B --> E["5"]
    C --> F["6"]
    C --> G["9"]
    D --> H["8"]

맞바꾸는 횟수는 많아야 층 수만큼입니다. 넣기가 O(log n) 인 까닭입니다.

꺼낼 때 내려가는 길

꺼낼 항목은 언제나 뿌리입니다. 뿌리를 꺼내면 빈 뿌리를 채워야 합니다. 이때 배열 맨 끝 항목을 뿌리로 옮겨서 트리에 빈칸이 생기지 않게 합니다.

옮겨 온 항목은 대개 자식보다 덜 급합니다. 그래서 두 자식 중 더 급한 쪽과 맞바꾸며 한 층씩 내려갑니다. 더 급한 쪽과 바꿔야 새 부모가 남은 자식보다도 급해집니다. 두 자식보다 급하거나 맨 아래에 닿으면 멈춥니다.

방금 1 을 넣은 힙에서 꺼내면 1 이 나옵니다. 그다음 맨 끝의 8 이 뿌리로 옮겨 옵니다. 아래가 옮겨 온 직후의 모양입니다. 그림에 적은 번호가 8 이 내려가는 길입니다.

flowchart TD
    A["8"] -->|"① 2 와 맞바꿈"| B["2"]
    A --> C["3"]
    B -->|"② 4 와 맞바꿈"| D["4"]
    B --> E["5"]
    C --> F["6"]
    C --> G["9"]

8 은 두 자식 2 와 3 가운데 더 급한 2 와 맞바꿉니다. 3 과 바꾸면 3 이 2 의 부모가 되어 규칙이 깨집니다. 다음에는 두 자식 4 와 5 가운데 더 급한 4 와 맞바꿉니다. 8 은 자식이 없는 3번 칸에 닿아 멈춥니다.

힙은 처음 그림의 모양으로 돌아옵니다. 내려가는 길도 층 수를 넘지 않습니다. 꺼내기 역시 O(log n) 입니다.

Python 의 heapq

Python 표준 라이브러리의 heapq 모듈은 리스트 위에 가장 작은 값이 뿌리에 오는 힙을 만들어 줍니다. 앞에서 본 작업 세 개를 (우선순위, 작업) 짝으로 넣고 꺼내 봅니다.

import heapq

q = []
heapq.heappush(q, (3, "메일 발송"))
heapq.heappush(q, (1, "결제 확인"))
heapq.heappush(q, (2, "썸네일 만들기"))
q[0]              # (1, '결제 확인')
heapq.heappop(q)  # (1, '결제 확인')
heapq.heappop(q)  # (2, '썸네일 만들기')
heapq.heappop(q)  # (3, '메일 발송')

짝끼리는 첫 값을 먼저 견줍니다. 그래서 앞에 둔 우선순위 숫자가 꺼내는 순서를 정합니다. q[0] 은 꺼내지 않고 뿌리를 들여다봅니다.

Java에서는 java.util.PriorityQueue 가 같은 일을 합니다. 비교 방법을 따로 주지 않으면 이것도 가장 작은 값부터 꺼냅니다.

같은 순위끼리의 순서

힙은 순위가 같은 항목끼리 들어온 순서를 지켜 주지 않습니다. 위아래로 맞바꾸는 동안 순서가 뒤섞이기 때문입니다.

같은 순위 안에서도 먼저 온 것을 먼저 꺼내야 한다면 번호를 하나 더 붙입니다. 넣을 때마다 1씩 느는 번호를 두고 (우선순위, 번호, 작업) 으로 넣습니다. 그러면 순위가 같을 때 번호가 순서를 정합니다.

쓰이는 곳

그래프에서 가장 짧은 길을 찾는 다익스트라 알고리즘이 대표적입니다. 그래프는 여러 지점(정점)과 그 사이를 잇는 길로 이루어진 구조입니다. 지도의 교차로와 도로를 떠올리면 됩니다. 이 지점은 앞에서 본 힙의 노드와 다른 것입니다.

다익스트라 알고리즘은 출발점에서 가장 가까운 지점부터 하나씩 거리를 정해 갑니다. 아직 거리를 정하지 않은 지점을 출발점까지의 거리와 함께 우선순위 큐에 넣어 둡니다. 그러면 꺼낼 때마다 그중 가장 가까운 지점이 나옵니다.

서버 쪽에서는 작업 큐가 급한 일을 먼저 처리할 때 씁니다. 결제 확인처럼 사용자가 기다리는 일을, 메일 발송처럼 늦어도 되는 일보다 먼저 꺼냅니다.

타이머를 여럿 관리할 때도 씁니다. 만료 시각을 우선순위로 넣으면 뿌리에는 언제나 가장 먼저 만료될 타이머가 있습니다. 다음에 깨어날 시각을 정할 때 뿌리 하나만 보면 됩니다. 그 시각이 되면 뿌리의 타이머를 꺼내 실행합니다.

큐잉 이론은 기다리는 줄이 얼마나 길어지고 얼마나 기다리는지를 따지는 분야입니다. 줄에서 누구를 먼저 처리할지 정하는 규칙도 그 대상입니다. 먼저 온 순서 대신 우선순위 규칙을 두면 급한 일의 대기 시간이 줄어듭니다. 반면 덜 급한 일의 대기 시간은 늘어납니다.

순위가 낮은 일이 밀리는 문제

급한 일이 끊이지 않고 들어오면 순위가 낮은 일은 한 번도 꺼내지지 못할 수 있습니다. 이렇게 차례가 영영 오지 않는 상태를 기아(starvation)라고 부릅니다.

흔한 처방은 기다린 시간만큼 순위를 조금씩 올려 주는 것입니다. 이 방법을 에이징(aging)이라고 부릅니다. 오래 기다린 일은 결국 새로 들어온 급한 일보다 앞서게 됩니다.

다른 구조가 맞는 경우

순위가 몇 단계뿐이면 단계마다 보통 큐를 하나씩 두는 방법이 단순합니다. 높음·보통·낮음 세 줄을 두고 높은 줄부터 확인하면 됩니다. 한 줄 안에서는 들어온 순서도 지켜집니다.

힙은 가장 급한 항목 말고는 찾기 어렵습니다. 특정 항목을 찾거나 중간 항목의 순위를 바꾸려면 배열을 처음부터 훑어야 해서 O(n) 이 듭니다.

각 항목이 지금 몇 번 칸에 있는지 따로 적어 두면 훑지 않고 바로 찾아 순위를 고칠 수 있습니다. 찾기 자체가 잦은 일이면 이진 탐색 트리 같은 다른 구조를 씁니다.

순위가 필요 없고 들어온 차례면 충분하다면 보통 큐를 씁니다. 큐는 넣기와 꺼내기를 둘 다 O(1) 에 끝냅니다.

관련 항목

우선순위 큐가 속하는 상위 분류

자료구조 · 추상 자료형 · 컬렉션 · 선형 자료구조

우선순위 큐를 만드는 밑감 자료구조

힙 (자료구조) · 이진 힙 · 완전 이진 트리 · 트리 · 배열 · 이진 탐색 트리 · 이항 힙 · 피보나치 힙

우선순위 큐와 꺼내는 규칙이 다른 자료구조

큐 · 스택 · 덱

우선순위 큐를 부르는 알고리즘

다익스트라 알고리즘 · 프림 알고리즘 · 힙 정렬 · 허프만 코딩 · 최단 경로 · 그래프

우선순위 큐로 처리 순서를 정하는 시스템 기술

작업 큐 · 스케줄링 · 타이머 · 이벤트 루프 · 메시지 큐

우선순위 규칙이 일으키는 장애와 처방

기아 · 에이징 · 우선순위 역전 · 헤드 오브 라인 블로킹

우선순위 큐의 비용과 대기를 따지는 이론

빅오 표기법 · 시간 복잡도 · 큐잉 이론 · 리틀의 법칙

우선순위 큐를 기본으로 제공하는 언어와 라이브러리

Python · Java · heapq · PriorityQueue