힙과 우선순위 큐: 가장 작은 것을 빨리 꺼내기
할 일이 계속 들어오고, 그때마다 가장 급한 것 하나를 먼저 처리해야 한다고 해 봅시다. 매번 전부 정렬하기는 아깝고, 매번 전부 훑기도 느립니다. 힙은 그 사이의 답입니다. 값을 넣고 꺼낼 때 트리와 배열이 한 걸음씩 어떻게 바뀌는지 보세요.
한 줄 답. 힙은 부모가 자식보다 작거나 같다는 규칙 하나만 지키는, 꽉 찬 모양의 완전 이진 트리(complete binary tree)입니다. 그래서 맨 위가 늘 가장 작은 값이고, 보는 데 한 걸음입니다. 넣을 때는 끝에 붙여 위로 올리고(sift-up), 꺼낼 때는 끝 값을 맨 위로 옮겨 아래로 내립니다(sift-down). 트리의 높이가 log n 이라 둘 다 많아야 log n 걸음입니다. 이렇게 「가장 작은(급한) 것부터 꺼내는 통」을 우선순위 큐라고 부릅니다.
처음에는 5, 3, 8, 1, 9, 2 를 차례로 넣는 걸음이 들어 있습니다. 「다음」으로 한 걸음씩 넘기세요. 「값 넣기」(0 ~ 99)와 「가장 작은 것 꺼내기」는 지금 걸음들을 끝까지 마친 힙에 이어서 하고, 그 일의 걸음을 처음부터 보여 줍니다. 트리의 동그라미와 아래 배열 칸은 같은 것입니다. 같은 층은 같은 색이고, 숫자 아래 작은 글자가 칸 번호입니다. 그림 읽기: 주황 테두리는 이번 걸음에 보는 칸이고 주황 점선이 트리의 노드와 같은 배열 칸을 잇습니다. 양쪽 화살표와 기호(8 > 2)는 비교, 굽은 화살표 둘은 자리 교환, 한쪽 화살표는 값 옮기기, 흐린 점선 동그라미는 빈자리입니다. 비교와 교환은 따로 한 걸음입니다.
해 볼 것. ① 「다음」을 17 번 누르면 배열이 [1, 3, 2, 5, 9, 8] 이 됩니다. 5절의 표와 같습니다. 정렬은 안 됐지만 맨 위는 가장 작은 1 입니다. ② 「가장 작은 것 꺼내기」를 누르고 끝까지 넘기면 4 걸음 만에 [2, 3, 8, 5, 9] 가 됩니다. ③ 0 을 넣어 보세요. 층이 3 개라 위로 두 번 교환하고 맨 위에 닿습니다. ④ 15 칸을 다 채워도 층은 4 개라 위로 올리기는 많아야 세 번입니다.
1. 힙이란: 규칙 둘
여기서 말하는 힙은 이진 힙입니다. 자식이 많아야 둘인 트리에 값을 담고, 두 규칙을 지킵니다.
- 힙 순서(heap order): 부모 ≤ 자식. 어느 칸이든 자기 자식들보다 작거나 같습니다. 이 규칙을 이어 보면 맨 위(루트, root)가 모든 값 가운데 가장 작습니다. 이것을 최소 힙이라고 부릅니다. 부등호를 뒤집으면 맨 위가 가장 큰 최대 힙입니다.
- 모양 규칙: 완전 이진 트리. 위 줄부터 채우고, 한 줄 안에서는 왼쪽부터 채웁니다. 맨 아래 줄만 오른쪽이 비어 있을 수 있습니다.
순서 규칙은 위아래만 봅니다. 형제끼리, 다른 가지끼리는 어느 쪽이 커도 됩니다. 그래서 힙은 정렬된 상태가 아닙니다. 그 대신 지키기가 쉽고, 맨 위가 가장 작다는 것 하나는 늘 확실합니다.
2. 배열에 담기: 자식은 2i + 1, 2i + 2
모양 규칙 덕분에 트리를 배열 하나에 빈칸 없이 담을 수 있습니다. 위 줄부터, 왼쪽부터 칸 0, 1, 2, … 를 매기면 됩니다. 실험에서 같은 색끼리 보면 트리의 한 층이 배열의 이어진 칸이 됩니다.
| 칸 i 에서 | 가는 곳 | 예: i = 1 |
|---|---|---|
| 왼쪽 자식 | 2i + 1 | 3 |
| 오른쪽 자식 | 2i + 2 | 4 |
| 부모 | (i − 1) ÷ 2 의 몫 | 0 |
칸끼리를 잇는 주소(포인터)를 따로 둘 필요가 없습니다. 덧셈과 곱셈으로 바로 갑니다. 칸 번호를 1 부터 매기는 책(출처의 algs4)에서는 자식이 2k, 2k + 1, 부모가 k ÷ 2 입니다. 같은 것을 다르게 센 것입니다.
3. 넣기와 꺼내기
넣기: 끝에 붙이고 위로 올리기
- 새 값을 배열 맨 끝(트리의 맨 아래 줄, 왼쪽부터 첫 빈자리)에 붙입니다. 모양 규칙이 지켜집니다.
- 부모와 비교합니다. 새 값이 부모보다 작으면 둘을 교환합니다.
- 바뀐 자리에서 다시 2 를 합니다. 부모보다 크거나 같거나, 맨 위에 닿으면 멈춥니다.
꺼내기: 맨 위를 빼고 끝 값을 올려 아래로 내리기
- 맨 위(칸 0)의 값을 꺼냅니다. 가장 작은 값입니다.
- 배열 맨 끝 값을 맨 위로 옮기고 끝 칸을 지웁니다. 모양 규칙은 지켜지지만 순서 규칙이 깨질 수 있습니다.
- 두 자식 가운데 작은 쪽과 비교합니다. 자기가 더 크면 교환합니다. 큰 쪽과 교환하면 새 부모가 다른 자식보다 커져 규칙이 다시 깨집니다.
- 바뀐 자리에서 다시 3 을 합니다. 작은 자식보다 작거나 같거나, 자식이 없으면 멈춥니다.
맨 위 보기는 칸 0 을 읽기만 하면 되니 한 걸음입니다.
4. 왜 log n 걸음인가: 트리의 높이
위로 올리기는 한 걸음에 한 층씩 올라가고, 아래로 내리기는 한 걸음에 한 층씩 내려갑니다. 그러니 걸음 수는 많아야 층의 수 − 1 입니다. 완전 이진 트리는 층마다 칸이 두 배(1, 2, 4, 8, …)라서, 값이 n 개면 층은 ⌊log₂ n⌋ + 1 개입니다.
| 값의 수 n | 층의 수 | 넣기·꺼내기에서 교환 횟수(많아야) |
|---|---|---|
| 15 | 4 | 3 |
| 1,000 | 10 | 9 |
| 1,000,000 | 20 | 19 |
꺼내기는 한 층마다 두 자식을 서로 비교하고 작은 쪽을 자기와 비교해서, 비교 횟수로는 넣기의 두 배쯤입니다. 그래도 값이 백만 개일 때 수십 번입니다. n 이 두 배가 되면 층이 하나 늘어 한 걸음 더 걸릴 뿐입니다(O(log n)).
재어 본 것. 이 쪽의 계산과 같은 방법으로 0 ~ n − 1 을 마구잡이 순서로 넣고 모두 꺼내 보았습니다(고정 씨앗). 넣기 한 번에 위로 교환한 횟수의 평균은 n = 1,000 에서 1.15, n = 1,000,000 에서 1.28 이었습니다. 새 값은 대개 아래쪽에 머뭅니다. 꺼내기 한 번에 아래로 교환한 횟수의 평균은 7.34(10 층), 17.31(20 층)로 거의 바닥까지 내려갔습니다. 끝에서 올라온 값은 대개 큰 값이기 때문입니다.
5. 손으로 따라가기
실험 ① 의 처음 입력 5, 3, 8, 1, 9, 2 를 빈 힙에 차례로 넣고, 마지막에 한 번 꺼냅니다.
| 한 일 | 걸음 | 끝난 뒤 배열 |
|---|---|---|
| 5 넣기 | 빈 힙이라 칸 0 에 놓음 | [5] |
| 3 넣기 | 맨 끝 빈칸인 칸 1 에 놓음. 3 < 부모 5 라 교환. 맨 위에 닿아 멈춤 | [3, 5] |
| 8 넣기 | 맨 끝 빈칸인 칸 2 에 놓음. 8 ≥ 부모 3 이라 멈춤 | [3, 5, 8] |
| 1 넣기 | 맨 끝 빈칸인 칸 3 에 놓음. 1 < 부모 5(칸 1)라 교환. 1 < 부모 3(칸 0)이라 교환. 맨 위에 닿아 멈춤 | [1, 3, 8, 5] |
| 9 넣기 | 맨 끝 빈칸인 칸 4 에 놓음. 9 ≥ 부모 3(칸 1)이라 멈춤 | [1, 3, 8, 5, 9] |
| 2 넣기 | 맨 끝 빈칸인 칸 5 에 놓음. 2 < 부모 8(칸 2)이라 교환. 2 ≥ 부모 1 이라 멈춤 | [1, 3, 2, 5, 9, 8] |
| 꺼내기 | 가장 작은 1 을 꺼내고, 모양을 지키려고 끝 값 8 을 맨 위로: [8, 3, 2, 5, 9]. 자식 3, 2 가운데 작은 2(칸 2)와 비교해 8 > 2 라 교환. 칸 2 의 자식 자리(칸 5, 6)는 비어 있어 멈춤 | [2, 3, 8, 5, 9] |
6. 꼭 알아야 할 성질
| 성질 | 쉬운 말 |
|---|---|
| 맨 위가 가장 작다 | 가장 작은 것을 보는 데 한 걸음. 두 번째로 작은 것은 맨 위의 자식 둘 가운데 하나다 |
| 정렬된 상태가 아니다 | 위아래만 순서가 있다. 「7 이 들어 있나」를 찾으려면 다 훑어야 한다(n 걸음) |
| 배열 하나로 된다 | 꽉 찬 모양이라 빈칸 없이 담기고, 자식·부모는 칸 번호 계산으로 찾는다. 더 드는 메모리가 없다 |
| 넣기·꺼내기가 log n | 트리의 높이만큼만 움직인다 |
| 같은 값의 순서를 지키지 않는다 | 먼저 넣은 것이 먼저 나온다는 보장이 없다(자주 묻는 것 3) |
7. 힙 정렬: 다 넣고 하나씩 꺼내기
힙에서 꺼내면 늘 남은 것 가운데 가장 작은 값이 나옵니다. 그러니 값을 다 넣고 하나씩 꺼내 늘어놓으면 작은 것부터 정렬된 줄이 됩니다. 넣기 n 번, 꺼내기 n 번이 각각 log n 이라 모두 n log n 입니다. 아래 실험은 한 걸음이 넣기 하나, 꺼내기 하나입니다(그 안의 올리기·내리기는 실험 ① 에서 본 대로입니다).
해 볼 것. 값은 7, 2, 9, 4, 1, 8, 3, 6 입니다. ① 「다음」을 8 번 누르면 다 넣은 힙 [1, 2, 3, 6, 4, 9, 8, 7] 이 됩니다. 정렬되지 않았습니다. ② 한 번 더 누르면 1 이 나오고 힙은 [2, 4, 3, 6, 7, 9, 8] 입니다. ③ 끝까지 누르면 꺼낸 줄이 1, 2, 3, 4, 6, 7, 8, 9 입니다.
이 방법은 힙을 따로 만들어 값 n 개만큼 메모리가 더 듭니다. 책의 힙 정렬(출처의 algs4)은 맨 위가 가장 큰 최대 힙을 같은 배열 안에서 만들고, 꺼낸 가장 큰 값을 배열 맨 뒤부터 채워서 메모리를 더 쓰지 않습니다. 어느 쪽이든 같은 값끼리의 순서는 지키지 않습니다(안정하지 않다). 다른 정렬과의 비교는 병합 정렬과 퀵 정렬 쪽에 있습니다.
8. 언제 무엇을 쓰나
「넣기」와 「가장 작은 것 꺼내기」를 되풀이하는 통(우선순위 큐)을 세 가지로 만들어 비교합니다. 칸의 숫자는 걸음 수의 크기입니다. 1 은 n 과 상관없이 몇 걸음(O(1)), log n 은 n 이 두 배가 돼도 한 걸음 더(O(log n)), n 은 n 이 두 배면 두 배(O(n)).
| 담는 법 | 넣기 최선 · 평균 · 최악 | 가장 작은 것 꺼내기 최선 · 평균 · 최악 | 맨 위 보기 | 더 드는 메모리 | 좋은 점 · 나쁜 점 | 쓰는 경우 |
|---|---|---|---|---|---|---|
| 그냥 리스트(끝에 붙이기) | 1 · 1 · 1 | n · n · n | n | 없음 | 넣기가 가장 빠르다 · 꺼낼 때마다 다 훑는다 | 값이 몇 개 안 되거나 꺼내기가 드물 때 |
| 정렬된 리스트(가장 작은 것이 끝에 오게) | 1 · n · n | 1 · 1 · 1 | 1 | 없음 | 꺼내기가 빠르고 전체 순서도 있다 · 넣을 때 자리를 만들려고 값을 민다 | 한 번 채우고 거의 꺼내기만 할 때, 순서대로 다 훑어야 할 때 |
| 이진 힙 | 1 · 1 · log n | 1 · log n · log n | 1 | 없음(배열 그대로) | 넣기와 꺼내기가 모두 빠르다 · 맨 위 말고는 순서가 없어 찾기는 n | 넣기와 꺼내기가 섞여 계속 일어날 때 |
힙의 「넣기 평균 1」은 마구잡이 순서로 넣을 때 위의 「재어 본 것」에서 평균 1.15 ~ 1.28 번 교환한 것을 뜻합니다. 「꺼내기 최선 1」은 같은 값이 많아 끝 값이 맨 위에서 바로 멈출 때입니다. 정렬된 리스트의 「넣기 최선 1」은 새 값이 가장 작아 끝에 바로 붙을 때입니다.
9. Python 코드
위의 절차를 그대로 옮긴 것입니다. 실험 ① 과 같이 5, 3, 8, 1, 9, 2 를 넣으면 [1, 3, 2, 5, 9, 8], 한 번 꺼내면 1 이 나오고 [2, 3, 8, 5, 9] 가 남습니다.
def push(heap, x):
heap.append(x)
i = len(heap) - 1
while i > 0 and heap[i] < heap[p := (i - 1) // 2]: # 부모보다 작으면 위로
heap[i], heap[p] = heap[p], heap[i]
i = p
def pop(heap):
top, heap[0] = heap[0], heap[-1] # 끝 값을 맨 위로
heap.pop()
i = 0
while (c := 2 * i + 1) < len(heap):
if c + 1 < len(heap) and heap[c + 1] < heap[c]: c += 1 # 작은 자식
if heap[i] <= heap[c]: break
heap[i], heap[c] = heap[c], heap[i]
i = c
return top
def heap_sort(xs): # 7절의 방법: 다 넣고 하나씩 꺼낸다
heap = []
for x in xs:
push(heap, x)
return [pop(heap) for _ in xs]
print(heap_sort([7, 2, 9, 4, 1, 8, 3, 6])) # [1, 2, 3, 4, 6, 7, 8, 9]
실제로는 표준 라이브러리의 heapq 를 씁니다. 그냥 리스트를 최소 힙으로 다루고, heap[0] 이 가장 작은 값입니다.
import heapq
heapq.heappush(h, 4); smallest = heapq.heappop(h) # 넣기, 가장 작은 것 꺼내기
heapq.heapify(xs) # 리스트를 그 자리에서 힙으로(n 걸음)
heapq.nlargest(3, [7, 2, 9, 4, 1, 8, 3, 6]) # [9, 8, 7]
heapify 는 하나씩 넣는 것(n log n)보다 빠른 n 걸음(선형 시간)에 힙을 만든다고 문서에 적혀 있습니다.
어디에 쓰나
- 작업 큐의 우선순위. 급한 일부터 처리하는 큐, 가장 먼저 울려야 할 타이머를 고르는 일. 일이 계속 들어오고 계속 꺼내지는 곳입니다.
- 가장 큰 k 개. 크기 k 의 최소 힙을 두고, 새 값이 맨 위보다 크면 맨 위를 꺼내고 새 값을 넣습니다. 끝나면 힙에 가장 큰 k 개가 남습니다. 값 n 개를 다 정렬하지 않고 n log k 걸음에 됩니다.
heapq.nlargest가 이 일을 합니다. - 가장 짧은 길 찾기. 다익스트라는 「지금까지 거리가 가장 짧은 곳」을 되풀이해 꺼내는데, 그 통이 힙입니다.
- 정렬. 7절의 힙 정렬.
자주 묻는 것
힙은 정렬된 상태인가요?
아닙니다. 힙이 지키는 것은 부모와 자식 사이의 순서뿐입니다. 형제끼리나 다른 가지끼리는 순서가 없습니다. 배열 [1, 3, 2, 5, 9, 8] 은 정렬되지 않았지만 힙입니다. 확실한 것은 맨 위가 가장 작다는 것 하나입니다.
가장 큰 것을 먼저 꺼내려면 어떻게 하나요?
규칙을 거꾸로 해서 부모가 자식보다 크거나 같게 만든 최대 힙을 씁니다. 하는 일은 같고 비교하는 방향만 반대입니다. Python 의 heapq 에는 3.14 판부터 heappush_max, heappop_max 같은 최대 힙 함수가 있습니다. 그 전 판에서는 숫자라면 흔히 값에 마이너스를 붙여 넣고 꺼낸 뒤 다시 붙입니다.
우선순위가 같으면 넣은 순서대로 나오나요?
보장되지 않습니다. 위로 올리고 아래로 내리는 동안 같은 값끼리의 순서가 바뀔 수 있습니다. 넣은 순서를 지키려면 heapq 문서처럼 (우선순위, 넣은 번호, 일) 묶음을 넣습니다. 우선순위가 같으면 번호가 작은 것이 먼저 나옵니다.
프로그램 메모리의 힙과 같은 것인가요?
이름만 같습니다. 프로그램이 실행 중에 메모리를 빌려 쓰는 영역도 힙이라고 부르지만, 이 쪽의 자료 구조와는 관계가 없습니다.
낱말
| 여기서 쓴 말 | 책에서 부르는 말 |
|---|---|
| 가장 작은(급한) 것부터 꺼내는 통 | 우선순위 큐(priority queue) |
| 힙, 맨 위가 가장 작은 힙 | 이진 힙(binary heap), 최소 힙(min-heap). 반대는 최대 힙(max-heap) |
| 부모 ≤ 자식 규칙 | 힙 순서(heap order), 힙 불변식(heap invariant) |
| 꽉 찬 모양의 트리 | 완전 이진 트리(complete binary tree) |
| 맨 위 | 루트(root) |
| 위로 올리기 | swim, sift-up, 상향식 힙 복구 |
| 아래로 내리기 | sink, sift-down, 하향식 힙 복구 |
| 맨 위 보기 | peek, find-min |
| 리스트를 그 자리에서 힙으로 | 힙 만들기(heapify, heap construction) |
| 다 넣고 하나씩 꺼내 정렬 | 힙 정렬(heapsort) |
| 같은 값의 순서를 지킴 | 안정 정렬(stable sort) |
출처
- Robert Sedgewick, Kevin Wayne, Algorithms, 4th Edition, 2.4 Priority Queues. 이진 힙, 배열에 담는 법, swim·sink, 힙 정렬, 정렬된·정렬 안 된 배열과의 비교.
- Python 문서, heapq: Heap queue algorithm. heappush, heappop, heapify(선형 시간), nlargest, 최대 힙 함수(3.14), 우선순위 큐를 만드는 법.