이진 힙

이진 힙은 모아 둔 값 가운데 가장 작은 값을 언제든 바로 확인하고 빠르게 꺼내 주는 자료구조입니다. 값이 들어오거나 빠질 때 전부 다시 정렬하지 않습니다. 몇 번만 맞바꿔서 가장 작은 값이 늘 맨 위에 오게 합니다. 급한 일부터 처리하는 줄을 만들 때 가장 흔히 씁니다.

상세

이 절은 값 일곱 개가 든 힙 하나로 두 규칙과 배열 표현, 넣기와 꺼내기, 드는 시간과 쓰임을 차례로 봅니다.

정렬해 두기와 전부 훑기 사이

가장 작은 값을 거듭 꺼내야 하는 일이 있습니다. 만료 시각이 가장 이른 타이머를 고르는 일이 그렇습니다.

값을 배열에 막 담아 두면 넣기는 끝에 붙이는 것으로 끝납니다. 대신 꺼낼 때마다 배열 전체를 훑어 가장 작은 값을 찾아야 합니다.

반대로 배열을 늘 정렬해 두면 가장 작은 값이 맨 앞에 있어서 꺼내기는 금방입니다. 대신 넣을 때마다 들어갈 칸을 찾아 뒤의 값을 한 칸씩 밀어야 합니다. 값이 백만 개면 어느 쪽이든 한 번 넣거나 꺼낼 때 값 백만 개 가까이를 건드립니다.

이진 힙은 그 중간을 택합니다. 값 전체를 정렬하지 않고 위아래 관계만 맞춰 둡니다. 그러면 값이 백만 개여도 넣기와 꺼내기가 스무 번 안팎의 맞바꿈으로 끝납니다.

트리와 노드

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

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

이진 힙에서 한 노드는 자식을 둘까지 둡니다. 이름의 「이진」이 이 둘을 가리킵니다.

부모와 자식 사이에 크기 순서를 정해 두는 트리들을 묶어 힙이라고 부릅니다. 이진 힙은 그 가운데 가장 흔한 종류입니다. 프로그램이 메모리를 빌려 쓰는 영역인 힙과는 이름만 같습니다.

힙이 지키는 두 규칙

첫째는 모양 규칙입니다. 트리는 위층부터 채웁니다. 한 층 안에서는 왼쪽부터 빈틈없이 채웁니다.

이런 트리를 완전 이진 트리라고 부릅니다. 맨 아래층만 오른쪽이 비어 있을 수 있습니다.

둘째는 순서 규칙입니다. 부모의 값은 언제나 자식의 값보다 작거나 같습니다. 이 규칙이 모든 부모와 자식 사이에서 지켜지면 가장 작은 값은 반드시 뿌리에 옵니다. 그래서 가장 작은 값을 보려면 뿌리 하나만 보면 됩니다.

아래는 값 일곱 개가 든 이진 힙입니다.

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

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

힙은 값 전체를 정렬해 두지 않습니다. 부모와 자식 사이만 맞춰 둡니다. 맞춰 둘 관계가 적어서 값이 들어오고 나갈 때 고칠 곳도 적습니다.

뿌리에 가장 작은 값을 두는 힙을 최소 힙이라고 부릅니다. 부등호를 뒤집어 가장 큰 값을 뿌리에 두면 최대 힙입니다. 둘은 비교 방향만 다르고 동작은 같습니다. 이 문서는 최소 힙으로 설명합니다.

배열 하나에 담는 방법

이진 힙은 노드끼리 포인터로 잇지 않습니다. 포인터는 다른 노드가 메모리 어디에 있는지 가리키는 값입니다. 이진 힙은 포인터 대신 배열 하나에 노드를 차례로 담습니다.

담는 순서는 뿌리부터입니다. 뿌리를 0번 칸에 둡니다. 그 아래로는 층마다 왼쪽부터 칸을 채웁니다. 앞의 힙에 칸 번호를 붙이면 이렇습니다.

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

칸 번호 순서로 늘어놓으면 배열은 [1, 4, 2, 7, 5, 6, 9] 입니다. 모양 규칙 덕분에 중간에 빈칸이 생기지 않습니다.

이렇게 담으면 칸 번호를 계산해서 부모와 자식을 찾습니다. i 번 칸의 두 자식은 2i+1 번과 2i+2 번 칸에 있습니다. 부모는 (i−1)÷2 번 칸입니다. 나눈 나머지는 버립니다.

1번 칸의 4 로 이 계산을 확인해 봅니다. 줄마다 오른쪽 주석이 그 줄이 내는 값입니다.

a = [1, 4, 2, 7, 5, 6, 9]
i = 1
a[2*i + 1]       # 7  왼쪽 자식
a[2*i + 2]       # 5  오른쪽 자식
a[(i - 1) // 2]  # 1  부모

계산한 자식 칸 번호가 배열 길이를 넘으면 그 노드는 자식이 없습니다. 3번 칸의 7 은 자식 칸이 7번과 8번입니다. 배열에는 6번 칸까지만 있습니다.

완전 이진 트리는 한 층 내려갈 때마다 칸 수가 두 배로 늡니다. 위 그림도 한 개, 두 개, 네 개로 늘어납니다. 그래서 값이 n 개면 층 수는 log₂ n 안팎입니다. log₂ n 은 2 를 몇 번 곱해야 n 이 되는지를 나타내는 수입니다.

넣을 때 위로 올라가는 길

새 값은 먼저 배열 맨 끝에 붙습니다. 트리로 보면 맨 아래층의 첫 빈칸입니다. 이것으로 모양 규칙은 지켜집니다. 하지만 새 값이 부모보다 작으면 순서 규칙이 깨집니다.

그래서 새 값을 부모와 비교합니다. 새 값이 더 작으면 둘을 맞바꿉니다. 한 층 올라간 새 값을 새 부모와 다시 비교합니다.

부모가 새 값보다 작거나 같거나, 뿌리에 닿으면 멈춥니다. 이 과정을 흔히 sift-up 이라고 부릅니다.

앞의 힙에 3 을 넣어 봅니다. 3 은 맨 끝인 7번 칸에 붙습니다. 트리로 보면 7 의 자식입니다. 그림에 적은 번호가 맞바꾸는 차례입니다.

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

3 은 부모 7 보다 작아서 맞바꿉니다. 올라간 3 은 새 부모 4 보다도 작아서 한 번 더 맞바꿉니다. 그 위의 부모 1 은 3 보다 작으므로 거기서 멈춥니다. 멈춘 뒤의 모양이 아래입니다.

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

배열로는 [1, 3, 2, 4, 5, 6, 9, 7] 입니다. 맞바꾸는 횟수는 많아야 층 수만큼입니다.

꺼낼 때 아래로 내려가는 길

꺼내는 값은 언제나 뿌리입니다. 뿌리를 꺼내면 맨 위가 빕니다. 이때 배열 맨 끝 값을 뿌리로 옮겨서 빈칸 없이 채웁니다.

옮겨 온 값은 대개 자식보다 큽니다. 그래서 두 자식 가운데 더 작은 쪽과 맞바꾸며 한 층씩 내려갑니다. 두 자식보다 작거나 같거나, 자식이 없는 맨 아래층에 닿으면 멈춥니다. 이 과정을 흔히 sift-down 이라고 부릅니다.

더 작은 자식을 고르는 데는 까닭이 있습니다. 더 큰 자식과 맞바꾸면 그 자식이 새 부모가 됩니다. 새 부모가 남은 자식보다 커서 순서 규칙이 곧바로 깨집니다.

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

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

7 의 두 자식은 3 과 2 입니다. 더 작은 2 와 맞바꿉니다.

내려간 7 의 두 자식은 6 과 9 입니다. 더 작은 6 과 맞바꿉니다. 7 은 자식이 없는 5번 칸에 닿아 멈춥니다. 멈춘 뒤의 모양이 아래입니다.

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

뿌리에는 남은 값 가운데 가장 작은 2 가 올라와 있습니다. 내려가는 길도 층 수를 넘지 않습니다.

흩어진 값으로 한 번에 세우기

정렬 안 된 값 n 개가 배열로 먼저 주어질 때가 있습니다. 하나씩 넣어도 힙은 됩니다. 하지만 값마다 sift-up 으로 층 수만큼 올라갈 수 있어서 시간이 더 듭니다.

더 적게 드는 방법이 있습니다. 먼저 배열을 트리로 봅니다. 그리고 자식이 있는 노드 가운데 마지막 것부터 뿌리 쪽으로 거슬러 갑니다. 거쳐 가는 노드마다 sift-down 을 합니다.

이 방법을 흔히 heapify 라고 부릅니다. [5, 9, 2, 7, 1] 로 해 봅니다. 그림의 번호가 맞바꾸는 차례입니다.

flowchart TD
    A["5"] --> B["9"]
    A --> C["2"]
    B --> D["7"]
    B -->|"① 1 과 맞바꿈"| E["1"]

자식이 있는 마지막 노드는 1번 칸의 9 입니다. 9 의 자식 7 과 1 가운데 더 작은 1 과 맞바꾸면 [5, 1, 2, 7, 9] 가 됩니다. 맞바꾼 뒤의 모양이 아래입니다.

flowchart TD
    A["5"] -->|"② 1 과 맞바꿈"| B["1"]
    A --> C["2"]
    B --> D["7"]
    B --> E["9"]

다음은 0번 칸의 5 입니다. 자식 1 과 2 가운데 더 작은 1 과 맞바꿉니다. 내려간 5 의 자식 7 과 9 는 5 보다 커서 멈춥니다. 다 세운 모양이 아래입니다.

flowchart TD
    A["1"] --> B["5"]
    A --> C["2"]
    B --> D["7"]
    B --> E["9"]

배열로는 [1, 5, 2, 7, 9] 입니다. 두 규칙을 다 지킵니다.

이 방법이 적게 드는 까닭은 노드가 아래층에 몰려 있기 때문입니다. 멀리 내려갈 수 있는 노드일수록 수가 적습니다. 층별로 놓으면 이렇습니다.

노드 수와 내려갈 층 수를 층마다 곱해 모두 더해도 n 을 넘지 않습니다. 그래서 한 번에 세우는 데 드는 시간은 값 수에 비례합니다. 하나씩 넣는 방법은 값마다 층 수만큼 올라갈 수 있어서 이보다 더 듭니다.

연산마다 드는 시간

연산에 드는 시간은 빅오 표기법으로 적습니다. 값이 n 개일 때 시간이 n 을 따라 어떻게 늘어나는지만 보는 표기입니다.

O(1) 은 n 과 상관없이 일정합니다. O(log n) 은 층 수만큼 늡니다. O(n) 은 n 에 비례해 늡니다.

아래 표는 최악일 때를 기준으로 적었습니다.

첫 소절에서 본 두 배열 방법은 넣기와 꺼내기 가운데 한쪽이 O(n) 입니다. 이진 힙은 둘 다 O(log n) 에 맞춥니다.

공간은 값 n 개를 담는 배열 하나가 전부입니다. 노드마다 포인터를 둘 필요가 없어서 값 말고 따로 드는 메모리가 없습니다.

우선순위 큐와 표준 라이브러리

우선순위 큐는 넣은 차례가 아니라 급한 차례대로 꺼내 주는 자료형입니다. 이진 힙은 이 자료형을 만드는 가장 흔한 방법입니다. 우선순위를 값으로 삼아 최소 힙에 넣으면 뿌리에 가장 급한 항목이 옵니다.

Python 표준 라이브러리의 heapq 모듈은 일반 리스트를 그대로 최소 힙으로 다룹니다. 앞의 한 번에 세우기 예와 같은 값으로 해 봅니다.

import heapq

a = [5, 9, 2, 7, 1]
heapq.heapify(a)
a                 # [1, 5, 2, 7, 9]
heapq.heappush(a, 3)
a                 # [1, 5, 2, 7, 9, 3]
heapq.heappop(a)  # 1

heapify 는 앞에서 손으로 세운 것과 같은 배열을 만듭니다. heappush 로 넣은 3 은 부모 2 보다 커서 올라가지 않고 5번 칸에 머뭅니다. heappop 은 뿌리의 1 을 돌려줍니다.

Java의 java.util.PriorityQueue 도 배열 위에 이진 힙을 둡니다. 비교 방법을 따로 주지 않으면 가장 작은 값부터 꺼냅니다.

지도에서 가장 짧은 길을 찾는 다익스트라 알고리즘도 이 큐를 씁니다. 출발점에서 가장 가까운 지점부터 차례로 꺼내야 하기 때문입니다. 타이머를 여럿 관리할 때는 만료 시각을 값으로 넣습니다. 그러면 다음에 깨어날 시각은 뿌리 하나만 보면 압니다.

힙 정렬

힙 정렬은 이진 힙으로 배열을 정렬하는 방법입니다. 먼저 배열 전체를 최대 힙으로 세웁니다. 그러면 가장 큰 값이 0번 칸에 옵니다.

이제 0번 칸과 맨 끝 칸을 맞바꿉니다. 가장 큰 값이 맨 끝에 놓입니다. 이때부터 배열은 두 구간으로 나뉩니다.

배열 앞쪽은 아직 힙입니다. 맨 끝부터는 정렬이 끝난 값이 쌓이는 구간입니다. 맞바꿀 때마다 앞쪽 힙은 한 칸 줄어듭니다.

뿌리로 온 값은 앞쪽 힙 안에서만 sift-down 으로 내려갑니다. 힙이 빌 때까지 이것을 되풀이하면 배열이 작은 값부터 정렬됩니다.

꺼내기를 n 번 하므로 최악일 때도 O(n log n) 입니다. 정렬 결과를 같은 배열 안에 만들어서 추가 메모리가 거의 들지 않습니다.

대신 같은 값끼리의 원래 순서를 지키지 못합니다. 멀리 떨어진 칸끼리 맞바꾸기 때문입니다. 같은 값의 원래 순서를 지키는 정렬을 안정 정렬이라고 부릅니다. 힙 정렬은 안정 정렬이 아닙니다.

상위 k 개 고르기

값 n 개 가운데 가장 큰 k 개만 필요할 때가 있습니다. 조회수가 가장 많은 글 열 개를 고르는 일이 그렇습니다. 전부 정렬하지 않고 크기가 k 인 최소 힙 하나로 고릅니다.

값을 하나씩 보며 힙에 k 개가 찰 때까지는 넣기만 합니다. 그 뒤로는 새 값을 뿌리와 비교합니다. 뿌리는 지금까지 고른 k 개 가운데 가장 작은 값입니다. 새 값이 더 크면 뿌리를 꺼내고 새 값을 넣습니다.

최소 힙을 쓰는 까닭은 탈락시킬 후보가 늘 뿌리에 있기 때문입니다. 끝까지 보면 힙에는 가장 큰 k 개가 남습니다.

힙 크기가 k 로 묶여 있어서 한 번 꺼내고 넣는 데 O(log k) 가 듭니다. 전체는 O(n log k) 입니다. k 가 n 보다 훨씬 작으면 전부 정렬하는 O(n log n) 보다 적게 듭니다. 이렇게 상위 몇 개만 고르는 질의를 흔히 상위 N 질의라고 부릅니다.

정렬된 목록 여러 개 합치기

병합 정렬은 정렬된 목록 둘을 하나로 합치는 일을 되풀이합니다. 정렬된 목록이 k 개 있으면 한 번에 합칠 수도 있습니다. 이때 목록마다 맨 앞 값을, 어느 목록에서 왔는지와 함께 최소 힙에 넣어 둡니다.

뿌리를 꺼내면 전체에서 가장 작은 값이 나옵니다. 그 값이 온 목록에서 다음 값을 꺼내 힙에 넣습니다. 힙에는 언제나 목록마다 값이 하나씩만 들어 있어서 한 번 꺼내고 넣는 데 O(log k) 가 듭니다.

메모리에 다 안 들어가는 데이터를 조각으로 나눠 정렬한 뒤 합치는 방법을 외부 정렬이라고 부릅니다. 외부 정렬은 흔히 이 방법으로 조각들을 합칩니다.

이진 힙이 맞지 않는 연산

특정 값을 찾는 데는 시간이 많이 듭니다. 순서 규칙은 부모와 자식 사이만 정하므로 찾는 값이 어느 가지에 있는지 알 수 없습니다. 배열을 처음부터 훑어야 해서 O(n) 이 듭니다.

중간에 있는 값의 우선순위를 바꾸는 일도 먼저 그 값을 찾아야 합니다. 값마다 지금 몇 번 칸에 있는지를 따로 적어 두면 훑지 않고 바로 찾습니다. 찾은 뒤에는 위로 올리거나 아래로 내려서 규칙을 되살립니다.

값을 작은 순서대로 전부 보는 일도 바로는 안 됩니다. 배열의 순서는 정렬된 순서가 아니기 때문입니다. 정렬된 순서가 필요하면 하나씩 꺼내야 합니다.

두 힙을 하나로 합치려면 배열 둘을 이어 붙이고 다시 세워야 해서 O(n) 이 듭니다. 합치기가 잦으면 이항 힙이나 피보나치 힙처럼 합치기를 싸게 하도록 만든 힙을 씁니다. 찾기가 잦으면 이진 탐색 트리 같은 다른 구조를 씁니다.

관련 항목

이진 힙이 속하는 상위 분류

자료구조 · 힙 (자료구조) · 완전 이진 트리 · 트리

이진 힙의 하위 종류

최소 힙 · 최대 힙 · 최소-최대 힙

이진 힙에 거는 연산

sift-up · sift-down · heapify · decrease-key

이진 힙을 쓰는 자료형과 알고리즘

우선순위 큐 · 힙 정렬 · 다익스트라 알고리즘 · 프림 알고리즘 · 허프만 코딩 · 상위 N 질의 · 외부 정렬 · 병합 정렬 · 타이머

이진 힙과 같은 역할을 두고 겨루는 자료구조

이항 힙 · 피보나치 힙 · 페어링 힙 · d-ary 힙 · 스킵 리스트 · 레드-블랙 트리

이진 힙을 구현해 둔 표준 라이브러리

heapq · PriorityQueue · Python · Java

이진 힙의 비용을 재는 표기

빅오 표기법 · 시간 복잡도 · 공간 복잡도 · 로그

이진 힙으로 정렬할 때 따지는 성질

안정 정렬 · 제자리 정렬 · 비교 정렬

이진 힙과 이름이나 모양이 헷갈리는 이웃

힙 · 이진 탐색 트리 · 이진 트리