요약

응급실은 온 순서가 아니라 가장 급한 환자부터 부른다. 이렇게 “가장 작은(급한) 것부터 꺼내는 줄”이 우선순위 큐이고, 힙은 그것을 빠르게 만드는 방법이다. 넣기와 가장 작은 것 꺼내기가 모두 빠르다. 원소가 100만 개여도 스무 번이 안 되게 자리를 바꾸면 끝난다. 대신 가장 작은 것 말고 “세 번째로 작은 것”이나 “특정 값”을 찾거나 지우는 일은 빠르지 않다.

예시로 보기

파이썬의 heapq는 보통 리스트를 힙으로 쓴다. 5, 3, 8, 1을 차례로 넣는다.

일 리스트 맨 앞(가장 작은 값)
heappush(h, 5) [5] 5
heappush(h, 3) [3, 5] 3
heappush(h, 8) [3, 5, 8] 3
heappush(h, 1) [1, 3, 8, 5] 1
heappop(h) → 1 [3, 5, 8] 3

리스트가 정렬되어 있지는 않다([1, 3, 8, 5]). 하지만 맨 앞 h[0]은 늘 가장 작은 값이다. 리스트를 나무 모양으로 보면 까닭이 보인다. 칸 i의 아래 두 칸이 2i + 1, 2i + 2번이다.

        1          칸 0
      /   \
     3     8       칸 1, 2
    /
   5               칸 3

위에 있는 값은 바로 아래 값보다 크지 않다. 이 규칙(힙 불변식)만 지키면 맨 위가 가장 작다. 형제끼리(3과 8)는 순서를 따지지 않는다. 그래서 완전히 정렬하는 것보다 일이 적다.

넣고 꺼내는 방법

  • 넣기(위로 올리기): 맨 끝에 붙인 뒤, 부모(칸 (i − 1) // 2)보다 작으면 자리를 바꾸며 올라간다. 1을 넣을 때 [3, 5, 8, 1] → 부모 5와 바꿔 [3, 1, 8, 5] → 부모 3과 바꿔 [1, 3, 8, 5].
  • 꺼내기(아래로 내리기): 맨 위를 꺼내고, 맨 끝 값을 맨 위로 옮긴다. 두 자식 중 더 작은 쪽보다 크면 자리를 바꾸며 내려간다. [1, 3, 8, 5]에서 1을 꺼내면 [5, 3, 8] → 자식 3이 더 작아 바꿔 [3, 5, 8].
     A                 B                 C
     3                 3                (1)
    / \               / \               / \
   5   8      ->    (1)  8      ->     3   8
  /                 /                 /
(1)                 5                 5

A는 1을 맨 끝(칸 3)에 붙인 모습, B는 부모 5와 바꾼 뒤, C는 부모 3과 바꾼 뒤다. 괄호 친 1이 한 층씩 올라가고, 부모가 자기보다 크지 않은 자리에 닿거나 맨 위에 오면 멈춘다1.

나무의 층수는 원소 n개일 때 ⌊log₂ n⌋ + 1이다. 올리기·내리기는 한 층에 한 번씩이라 \(O(\log n)\)이다. 원소 100만 개면 층이 20개다.

코드 하는 일 비용2
heapq.heappush(h, x) 넣기 \(O(\log n)\)
heapq.heappop(h) 가장 작은 값 꺼내기 \(O(\log n)\)
h[0] 가장 작은 값 보기 \(O(1)\)
heapq.heapify(a) 리스트를 제자리에서 힙으로 \(O(n)\)
heapq.nsmallest(k, a) 가장 작은 k개 \(O(n \log k)\)
특정 값 찾기·지우기   \(O(n)\)
  • 최대 힙: heapq에는 최소 힙만 있다. 값에 −1을 곱해 넣고, 꺼낼 때 다시 −1을 곱한다.
  • 튜플 넣기: (우선순위, 내용)을 넣으면 앞 칸부터 비교한다. (1, “b”)와 (1, “a”)는 우선순위가 같아 둘째 칸을 비교하고, (1, “a”)가 먼저 나온다.
검증: 예시 표의 리스트 상태, 넣기·꺼내기 과정, 확인 문제 C1의 답, 최대 힙과 튜플 순서, heapify 결과를 확인했다. 직접 만든 최소 힙이 무작위 넣기·꺼내기 2,000묶음에서 heapq와 같은 값을 꺼내고 불변식을 늘 지켰다. 층수 공식도 n = 1 ~ 1,000에서 확인했다 — 12_heap_impl.py

활용

  • 쓰는 곳: 작업 스케줄러(급한 작업부터), 가장 가까운 곳부터 확정하는 최단 경로(다익스트라), 계속 들어오는 수의 중앙값, 정렬된 여러 목록 합치기(heapq.merge).
  • 계속 들어오는 수의 중앙값: 힙 두 개로 구한다. 작은 절반은 최대 힙, 큰 절반은 최소 힙에 두고 두 힙의 크기 차를 1 이하로 맞춘다. 그러면 넣기는 \(O(\log n)\)이고, 중앙값은 두 꼭대기에서 바로 읽는다(개수가 짝수면 두 꼭대기의 평균). 중앙값의 뜻과, 평균보다 극단값에 덜 흔들리는 까닭은 기술통계에 있다.
  • 고르는 기준: 값이 한 번에 다 주어지고 순서만 필요하면 한 번 정렬하면 된다. 값이 계속 들어오고 나가면서 그때그때 가장 작은 값이 필요하면 힙이다.
  • 지우기 대신 무시하기: 힙은 가운데 값을 지우기 어렵다. 그래서 값이 바뀌면 새 값을 또 넣고, 꺼냈을 때 이미 낡은 값이면 버린다. 이것을 늦은 삭제(lazy deletion)라 한다. 다익스트라에서 이렇게 쓴다.
  • 흔한 실수: 힙 리스트를 정렬된 리스트로 착각해 h[1]을 두 번째로 작은 값으로 쓴다. 최대 힙이 필요한데 부호를 안 뒤집는다. 딕셔너리처럼 크기를 비교할 수 없는 값을 튜플 둘째 칸에 넣어, 우선순위가 같고 내용이 다를 때 TypeError가 난다. 둘째 칸에 넣은 순서 번호를 끼워 (우선순위, 번호, 내용)으로 넣으면 피할 수 있다.

연결

  • 선수: 리스트와 문자열, 시간 복잡도로 방법 고르기
  • 대조: 큐는 먼저 넣은 것을, 힙은 가장 작은 것을 먼저 꺼낸다.
  • 층수 \(\lfloor \log_2 n \rfloor + 1\)(\(\lfloor\ \rfloor\)는 소수점 아래를 버린 정수)은 등비급수에서 나온다. k층을 꽉 채우면 \(1 + 2 + \cdots + 2^{k-1} = 2^k - 1\)칸이라, 층이 L개인 힙의 칸 수 n은 \(2^{L-1} \le n < 2^L\)이다. 거꾸로 칸 n개인 이진 트리는 어떻게 만들어도 높이(간선 수)가 \(\lfloor \log_2 n \rfloor\) 이상, 곧 층이 \(\lfloor \log_2 n \rfloor + 1\)개 이상이다(트리). 힙은 위층부터 빈틈없이 채워 이 가장 적은 층수를 지킨다.
  • 모든 칸 번호에 1을 더해 2진수로 보면, 왼쪽 자식은 끝에 0을, 오른쪽 자식은 끝에 1을 붙인 수이고 부모는 끝자리를 뗀 수다. 그래서 n칸 힙의 층수는 n의 2진 자릿수와 같다(진법과 자릿수).
  • heapify는 맨 아래 부모 칸부터 맨 위 칸까지 거꾸로 돌며 칸마다 내리기를 한다. 높이 \(h\)(잎은 0)인 칸은 대략 \(n/2^{h+1}\)개이고 각자 많아야 \(h\)층 내려가므로, 총비용은 대략 \(n\left(\frac14 + \frac28 + \frac{3}{16} + \cdots\right)\)이다. 이 급수는 급수의 수렴의 비 판정으로 수렴하니 비용은 n의 상수배다. 급수의 합은 정확히 1이고, 이 합 계산은 합의 계산과 어림의 힙 만들기 항목에 있다.
  • 함께 보면 좋은 수학: 로그(100만 개가 20층인 것은 \(\log_2 10^6 \approx 19.93\)이기 때문이다), 엔트로피(허프만 부호는 확률이 가장 작은 두 묶음을 힙에서 꺼내 합친 뒤 다시 넣기를 되풀이해 만든다)
  • 브리지: 트리 칸 번호 ↔ 2진법 자릿수

과목별 관점

자료구조 (1-2학기). 자료구조에서는 같은 힙을 C 배열로 만들면서 배열의 1번 칸부터 쓴다. 0번 칸은 비워 둔다. 이 문서의 heapq는 0번 칸부터 쓴다. 같은 나무이고 칸 번호만 하나씩 밀린다.

  이 문서 (0번 칸부터) 자료구조 (1번 칸부터)
뿌리 칸 0 칸 1
칸 i의 부모 (i − 1) // 2 i / 2의 몫
칸 i의 두 자식 2i + 1, 2i + 2 2i, 2i + 1
값 n개를 담는 칸 수 n n + 1

1번 칸부터 쓰는 쪽의 번호에서 1을 빼면 0번 칸부터 쓰는 쪽의 번호다. 1번 방식의 칸 4는 0번 방식의 칸 3이고, 그 자식인 칸 8·9는 칸 7·8이다3.

자료구조 쪽이 이 문서에 더하는 것은 두 가지다. 하나는 방향이다. 우선순위 큐를 가장 작은 것을 꺼내는 것(min priority queue)과 가장 큰 것을 꺼내는 것(max priority queue)으로 나누고, 할 수 있는 일을 empty, size, push, top, pop으로 적는다. heapq는 앞의 것이고, 자료구조의 예는 주로 뒤의 것(최대 힙)이다. 다른 하나는 만드는 법이다. 넣기와 꺼내기를 C로 직접 쓰되, 두 값을 맞바꾸는 대신 빈자리를 한 층씩 옮기고 값은 마지막에 한 번만 적는다: 최대 힙과 최소 힙. 힙으로 정렬하는 법은 우선순위 큐 정렬과 힙 정렬에, 가장 먼저 비는 기계를 힙으로 찾는 예는 LPT 스케줄링에 있다.

확인 문제

C1 빈 힙에 4, 7, 2, 9, 1을 차례로 heappush한 뒤의 리스트는? 이어서 heappop을 두 번 하면 무엇이 나오고 리스트는 어떻게 되는가?

답: [1, 2, 4, 9, 7]. 꺼내면 1, 2가 나오고 리스트는 [4, 7, 9]다. 흔한 오답은 넣은 뒤 리스트를 [1, 2, 4, 7, 9]처럼 정렬된 모양으로 쓰는 것이다. 힙은 부모·자식 사이만 맞추고 전체를 정렬하지 않는다.

C2 넣기와 꺼내기가 \(O(\log n)\)인 까닭은?

답: 힙은 위에서부터 층을 빈틈없이 채운 나무라 층수가 약 log₂ n이다. 넣기는 맨 아래에서 위로, 꺼내기는 맨 위에서 아래로 한 층에 한 번씩만 자리를 바꾼다. 그래서 바꾸는 횟수가 층수를 넘지 않는다.

C3 두 상황에 정렬과 힙 중 무엇이 알맞은가? (가) 점수 10만 개를 한 번 받아 높은 순으로 모두 출력한다. (나) 작업이 계속 들어오고, 그때마다 가장 급한 작업 하나를 꺼내 처리한다.

답: (가)는 정렬 한 번(\(O(n \log n)\))이면 끝난다. (나)는 힙이다. 새 작업이 들어올 때마다 다시 정렬하면 한 번에 \(O(n \log n)\)이지만, 힙은 넣기·꺼내기가 \(O(\log n)\)이다.

C4 리스트 [9, 8, 7, 6, 7, 2, 6, 5, 1]은 부모가 자식보다 작지 않은 최대 힙이다. 값 6(리스트의 칸 3)의 부모와 두 자식을 이 문서의 방식(0번 칸부터)으로 찾아라. 같은 값들을 1번 칸부터 넣은 C 배열에서는 6이 몇 번 칸이고, 부모와 자식은 몇 번 칸인가?

답: 0번 칸 방식: 6은 칸 3이다. 부모는 칸 (3 − 1) // 2 = 1의 8이고, 자식은 칸 7의 5와 칸 8의 1이다. 1번 칸 방식: 6은 칸 4다. 부모는 칸 4 / 2 = 2의 8이고, 자식은 칸 8의 5와 칸 9의 1이다. 칸 번호는 모두 1씩 다르고 가리키는 값은 같다.
이유: 두 방식의 식을 섞으면 틀린다. 0번 칸 방식에서 자식을 2i, 2i + 1로 찾으면 칸 6의 6과 칸 7의 5를 자식으로 잘못 읽는다3.

  1. ‘넣고 꺼내는 방법’ 절의 넣기 예 [3, 5, 8, 1] → [3, 1, 8, 5] → [1, 3, 8, 5]를 칸 i의 자식이 2i + 1, 2i + 2라는 규칙대로 나무로 그렸다. ↩

  2. Python 3 표준 라이브러리 문서, “heapq — Heap queue algorithm”: 모든 k에 대해 a[k] <= a[2*k+1], a[k] <= a[2*k+2]인 리스트, 가장 작은 값은 a[0], heapify는 선형 시간. 넣기·꺼내기의 O(log n)은 Laaksonen, Competitive Programmer’s Handbook (2018년 7월판), 4.5 “Other structures”의 Priority queue와 Cormen 외, Introduction to Algorithms 3판 6장. ↩

  3. 번호를 1씩 민 관계는 22_full-complete-binary-tree_verify.py로, 카드의 칸과 값은 27_max-heap_impl.c로 확인했다. ↩ ↩2