힙: 가장 큰 것 몇 개만

쇼핑몰 첫 화면에 "지금 인기 상품 10"이 있다. 상품마다 최근 한 시간 클릭 수로 점수를 매기고, 1분마다 상위 10개를 다시 뽑는다. 첫 구현은 이렇다.

const top10 = products.toSorted((a, b) => b.score - a.score).slice(0, 10)

상품이 100만 개면 1분마다 100만 개를 줄 세운 뒤 10개만 남기고 버린다. 필요한 것은 맨 앞 10개뿐이다. 우선순위가 높은 작업부터 처리하는 작업 큐도 같은 모양이다. 매번 가장 급한 것 하나만 꺼내면 되는데, 작업이 들어올 때마다 전체를 정렬할 필요가 있을까?

이 장은 "가장 작은(또는 큰) 것 하나"를 빠르게 꺼내는 자료 구조, 힙(heap)을 본다. 정의는 이진 힙과 우선순위 큐 노트에 있다.

힙: 배열에 담은 트리

이진 힙(binary heap)은 위층부터, 한 층 안에서는 왼쪽부터 빈틈없이 채운 이진 트리(binary tree, 노드마다 자식이 많아야 둘인 트리. 트리 용어는 『개발 수학』 Unit 10)다. 빈틈이 없어서 트리를 배열 하나에 층 순서대로 담을 수 있다. 0부터 세면 인덱스 i의 자식은 2i + 1과 2i + 2, 부모는 (i - 1) / 2를 내린 값이다(1번 칸의 부모는 (1 − 1) / 2 = 0, 4번 칸의 부모는 3 / 2 = 1.5 → 1). 자식·부모를 가리키는 참조를 따로 두지 않고 계산만으로 위아래를 오간다.

배열 [2, 5, 3, 9, 6]을 이 규칙으로 그리면 3층짜리 트리다.

      2        ← 0번 칸
    /   \
   5     3     ← 1번, 2번 칸
  / \
 9   6         ← 3번, 4번 칸

최소 힙(min-heap)은 여기에 조건 하나를 더 건다. 모든 부모는 자식보다 작거나 같다. 그래서 가장 작은 값은 늘 루트 heap[0]에 있다. 형제끼리, 다른 가지끼리는 순서를 따지지 않는다. 전체를 정렬해 두는 것보다 훨씬 느슨한 조건이고, 이 느슨함 덕분에 고치는 비용이 싸다.

Python 표준 라이브러리 heapq가 정확히 이 방식이다. 보통 리스트를 그대로 힙으로 쓰고, heap[k] <= heap[2*k+1], heap[k] <= heap[2*k+2]를 유지하며, heap[0]이 가장 작다(Python 문서: heapq). 최대 힙(max-heap) 함수(heappush_max 등)는 Python 3.14에 추가됐다. 그 전 버전에서는 값의 부호를 뒤집어 넣는 방법을 흔히 쓴다. JavaScript에는 내장 힙이 없다. 표준 내장 객체 목록의 컬렉션은 Array·형식화 배열·Map·Set·WeakMap·WeakSet뿐이다(MDN: Standard built-in objects). 그래서 이 장의 TypeScript 코드는 힙을 직접 짠다.

넣기와 꺼내기: 한 줄기만 고친다

넣을 때는 배열 맨 끝에 붙인다. 트리 모양은 여전히 빈틈이 없지만 새 값이 부모보다 작으면 힙 조건이 깨진다. 그러면 부모와 자리를 바꾸고, 다시 새 부모와 비교한다. 이렇게 위로 올라가는 동작을 위로 올리기(sift up)라고 한다.

1const heap: number[] = [2, 5, 3, 9, 6]2function add(x: number) {3  heap.push(x)4  let i = heap.length - 15  while (i > 0) {6    const p = Math.floor((i - 1) / 2)7    if (heap[p] <= heap[i]) break8    [heap[p], heap[i]] = [heap[i], heap[p]]9    i = p10  }11}12for (const x of [1]) add(x)13console.log(heap.join(' '))

1 5 2 9 6 3

꺼낼 때는 반대다. 루트를 꺼내면 맨 위가 빈다. 맨 끝 원소를 떼어 루트에 올리고(빈 칸이 트리 끝에서 생기게 하려는 것), 두 자식 중 더 작은 쪽보다 크면 자리를 바꾸며 내려간다. 이것이 아래로 내리기(sift down)다.

1const heap = [1, 2, 3, 9, 6, 5]2function take(): number {3  const top = heap[0]4  const last = heap.pop()!5  if (heap.length === 0) return top6  heap[0] = last7  let i = 08  while (true) {9    const left = 2 * i + 110    const right = left + 111    let m = i12    if (left < heap.length && heap[left] < heap[m]) m = left13    if (right < heap.length && heap[right] < heap[m]) m = right14    if (m === i) break15    [heap[m], heap[i]] = [heap[i], heap[m]]16    i = m17  }18  return top19}20for (let n = 0; n < 2; n++) {21  console.log(`꺼냄 ${take()} / 남은 힙 ${heap.join(' ')}`)22}

꺼냄 1 / 남은 힙 2 5 3 9 6
꺼냄 2 / 남은 힙 3 5 6 9

[1, 2, 3, 9, 6, 5]에서 1을 꺼내면 맨 끝의 5가 루트로 올라간다. 자식 2와 3 중 작은 2와 바꾸고, 다시 자식 9와 6 중 작은 6과 비교해 5가 더 작으니 멈춘다. 결과는 2 5 3 9 6이고 루트에는 다음으로 작은 2가 와 있다. 꺼내기도 한 줄기만 내려가니 O(log n)이다. 가장 작은 것을 보기만 할 때는 heap[0]을 읽으면 되니 O(1)이다.

정리하면 힙은 "가장 작은 것 하나"를 묻는 질문에만 빠르다. 3번째로 작은 값을 찾거나 특정 값을 찾으려면 배열 전체를 봐야 한다. 그 대신 넣기와 꺼내기가 모두 O(log n)이라서, 원소가 계속 들어오고 나가는 우선순위 큐(priority queue)의 표준 구현이 된다.

상위 k개: 크기 k짜리 최소 힙

1const scores = [12, 40, 7, 33, 25, 50, 18, 41]2const k = 33const heap = scores.slice(0, k).sort((a, b) => a - b)4function sink(i: number) {5  while (true) {6    const left = 2 * i + 17    const right = left + 18    let m = i9    if (left < heap.length && heap[left] < heap[m]) m = left10    if (right < heap.length && heap[right] < heap[m]) m = right11    if (m === i) return12    [heap[m], heap[i]] = [heap[i], heap[m]]13    i = m14  }15}16for (const x of scores.slice(k)) {17  if (x <= heap[0]) continue18  heap[0] = x19  sink(0)20}21console.log(heap.sort((a, b) => b - a).join(' '))

50 41 40

얼마나 아낄까

점수 n개에서 상위 k개를 고르는 비용을 견줘 보자. 7장에서 본 비교 정렬(comparison sort)은 전체 O(n log n)이니, 원소당으로 나누면 약 log₂ n번 비교한다(n = 100만이면 약 20번). 크기 k 힙은 원소마다 문턱과 한 번 비교하고, 들어갈 때만 높이 log₂ k만큼 내려가서 최악에도 O(n log k)다.

반대로 k가 n에 가까우면 이득이 사라진다. Python 문서도 heapq.nlargest·nsmallest는 고를 개수(이 장의 k)가 작을 때 가장 좋고, 클 때는 sorted()가 더 효율적이며, 하나만 필요하면 min()·max()가 낫다고 적는다(Python 문서: heapq). 상위 1개라면 힙도 필요 없이 한 번 훑으면 된다.

작업 큐에 쓸 때 하나 더 챙길 것이 있다. 힙은 우선순위가 같은 작업끼리 들어온 순서를 따로 기억하지 않는다. 올리기·내리기가 자리를 바꾸며 그 순서가 섞인다. Python 문서는 (우선순위, 들어온 순번, 작업)처럼 순번을 둘째 값으로 넣어 같은 우선순위는 먼저 들어온 것부터 나오게 하는 방법을 소개한다. 튜플은 앞 원소부터 견주고 같을 때만 다음 원소로 넘어가므로(7장 4절), 순번이 모두 다르면 비교가 셋째 값인 작업 객체까지 가는 일도 막는다.

코드 리뷰: 작업 큐

정리하면 느려지는 줄은 넣을 때마다 전체 정렬, shift()로 꺼내기, 상위 k개를 위해 전체 정렬이다. 힙이면 넣기·꺼내기가 O(log n), 상위 k개는 O(n log k)다.

5, 15, 1, 3, 8, 7
→ 5, 10, 5, 4, 5, 6