힙과 우선순위 큐: 가장 작은 것을 빨리 꺼내기

할 일이 계속 들어오고, 그때마다 가장 급한 것 하나를 먼저 처리해야 한다고 해 봅시다. 매번 전부 정렬하기는 아깝고, 매번 전부 훑기도 느립니다. 힙은 그 사이의 답입니다. 값을 넣고 꺼낼 때 트리와 배열이 한 걸음씩 어떻게 바뀌는지 보세요.

한 줄 답. 힙은 부모가 자식보다 작거나 같다는 규칙 하나만 지키는, 꽉 찬 모양의 완전 이진 트리(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. 힙이란: 규칙 둘

여기서 말하는 힙은 이진 힙입니다. 자식이 많아야 둘인 트리에 값을 담고, 두 규칙을 지킵니다.

  1. 힙 순서(heap order): 부모 ≤ 자식. 어느 칸이든 자기 자식들보다 작거나 같습니다. 이 규칙을 이어 보면 맨 위(루트, root)가 모든 값 가운데 가장 작습니다. 이것을 최소 힙이라고 부릅니다. 부등호를 뒤집으면 맨 위가 가장 큰 최대 힙입니다.
  2. 모양 규칙: 완전 이진 트리. 위 줄부터 채우고, 한 줄 안에서는 왼쪽부터 채웁니다. 맨 아래 줄만 오른쪽이 비어 있을 수 있습니다.

순서 규칙은 위아래만 봅니다. 형제끼리, 다른 가지끼리는 어느 쪽이 커도 됩니다. 그래서 힙은 정렬된 상태가 아닙니다. 그 대신 지키기가 쉽고, 맨 위가 가장 작다는 것 하나는 늘 확실합니다.

2. 배열에 담기: 자식은 2i + 1, 2i + 2

모양 규칙 덕분에 트리를 배열 하나에 빈칸 없이 담을 수 있습니다. 위 줄부터, 왼쪽부터 칸 0, 1, 2, … 를 매기면 됩니다. 실험에서 같은 색끼리 보면 트리의 한 층이 배열의 이어진 칸이 됩니다.

칸 i 에서가는 곳예: i = 1
왼쪽 자식2i + 13
오른쪽 자식2i + 24
부모(i − 1) ÷ 2 의 몫0
012 3456 0123 456 i = 1 2i + 1 = 3 2i + 2 = 4 (i − 1) ÷ 2 = 0 트리배열
칸 번호로 건너뛰기. 칸 i = 1 에서 왼쪽 자식은 2i + 1 = 3, 오른쪽 자식은 2i + 2 = 4, 부모는 (i − 1) ÷ 2 = 0 입니다. 위의 트리와 아래 배열에 같은 길을 그렸습니다. 배열에서는 칸 번호를 계산해 바로 건너뜁니다. 색은 층입니다.

칸끼리를 잇는 주소(포인터)를 따로 둘 필요가 없습니다. 덧셈과 곱셈으로 바로 갑니다. 칸 번호를 1 부터 매기는 책(출처의 algs4)에서는 자식이 2k, 2k + 1, 부모가 k ÷ 2 입니다. 같은 것을 다르게 센 것입니다.

3. 넣기와 꺼내기

넣기: 끝에 붙이고 위로 올리기

  1. 새 값을 배열 맨 끝(트리의 맨 아래 줄, 왼쪽부터 첫 빈자리)에 붙입니다. 모양 규칙이 지켜집니다.
  2. 부모와 비교합니다. 새 값이 부모보다 작으면 둘을 교환합니다.
  3. 바뀐 자리에서 다시 2 를 합니다. 부모보다 크거나 같거나, 맨 위에 닿으면 멈춥니다.

꺼내기: 맨 위를 빼고 끝 값을 올려 아래로 내리기

  1. 맨 위(칸 0)의 값을 꺼냅니다. 가장 작은 값입니다.
  2. 배열 맨 끝 값을 맨 위로 옮기고 끝 칸을 지웁니다. 모양 규칙은 지켜지지만 순서 규칙이 깨질 수 있습니다.
  3. 두 자식 가운데 작은 쪽과 비교합니다. 자기가 더 크면 교환합니다. 큰 쪽과 교환하면 새 부모가 다른 자식보다 커져 규칙이 다시 깨집니다.
  4. 바뀐 자리에서 다시 3 을 합니다. 작은 자식보다 작거나 같거나, 자식이 없으면 멈춥니다.
3581 1385 83259 23859 ①②①② →→ 1 을 꺼냄 넣기: ① 1 < 5 라 교환 ② 1 < 3 이라 교환, 맨 위라 멈춤 꺼내기: ① 끝 값 8 을 맨 위로 ② 8 > 작은 자식 2 라 교환
위로 올리기와 아래로 내리기. 위 줄은 [3, 5, 8] 에 1 을 넣을 때(칸 3 에 붙인 뒤), 아래 줄은 [1, 3, 2, 5, 9, 8] 에서 꺼낼 때입니다. 5절의 표와 같은 예입니다. 왼쪽은 움직이기 전, 오른쪽은 끝난 뒤이고, 주황 화살표는 움직이는 값이 지나간 길을 번호 순서로 보여 줍니다. 점선 동그라미는 끝 값이 떠난 빈자리입니다.

맨 위 보기는 칸 0 을 읽기만 하면 되니 한 걸음입니다.

4. 왜 log n 걸음인가: 트리의 높이

위로 올리기는 한 걸음에 한 층씩 올라가고, 아래로 내리기는 한 걸음에 한 층씩 내려갑니다. 그러니 걸음 수는 많아야 층의 수 − 1 입니다. 완전 이진 트리는 층마다 칸이 두 배(1, 2, 4, 8, …)라서, 값이 n 개면 층은 ⌊log₂ n⌋ + 1 개입니다.

값의 수 n층의 수넣기·꺼내기에서 교환 횟수(많아야)
1543
1,000109
1,000,0002019

꺼내기는 한 층마다 두 자식을 서로 비교하고 작은 쪽을 자기와 비교해서, 비교 횟수로는 넣기의 두 배쯤입니다. 그래도 값이 백만 개일 때 수십 번입니다. 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 · 1n · n · nn없음넣기가 가장 빠르다 · 꺼낼 때마다 다 훑는다값이 몇 개 안 되거나 꺼내기가 드물 때
정렬된 리스트(가장 작은 것이 끝에 오게)1 · n · n1 · 1 · 11없음꺼내기가 빠르고 전체 순서도 있다 · 넣을 때 자리를 만들려고 값을 민다한 번 채우고 거의 꺼내기만 할 때, 순서대로 다 훑어야 할 때
이진 힙1 · 1 · log n1 · log n · log n1없음(배열 그대로)넣기와 꺼내기가 모두 빠르다 · 맨 위 말고는 순서가 없어 찾기는 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 걸음(선형 시간)에 힙을 만든다고 문서에 적혀 있습니다.

어디에 쓰나

자주 묻는 것

힙은 정렬된 상태인가요?

아닙니다. 힙이 지키는 것은 부모와 자식 사이의 순서뿐입니다. 형제끼리나 다른 가지끼리는 순서가 없습니다. 배열 [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)

출처

← 병합 정렬과 퀵 정렬이진 탐색 →