yeolyi.com성열의 컴퓨터공학

힙

초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.

타이머로 할 일을 여러 개 예약하면 프로그램은 예약한 순서와 상관없이 시각이 가장 이른 일부터 실행해야 합니다. 먼저 넣은 것을 먼저 꺼내는 큐로는 안 됩니다. 알아야 할 것은 전체 순서가 아니라 지금 가장 이른 하나입니다.

우선순위 큐

넣은 순서와 상관없이 가장 급한 것부터 꺼내는 자료구조를 우선순위 큐(priority queue)라 합니다. 이 글에서는 시각처럼 숫자가 작을수록 급하다고 합시다.

정렬하지 않은 배열은 꺼낼 때마다 전체를 훑어야 하고, 정렬된 배열은 넣을 때마다 뒤의 값을 밀어야 합니다. AVL 트리는 둘 다 O(log n)에 하지만, 가장 작은 값 하나만 알면 되는데도 모든 값의 순서를 지키느라 회전을 합니다. 더 단순하게 할 수는 없을까요?

힙

힙(heap)은 이진 탐색 트리보다 규칙을 느슨하게 해서 이 문제를 풉니다. 값 규칙은 하나뿐입니다. 부모는 자식보다 작거나 같습니다. 그러면 가장 작은 값은 반드시 루트에 있습니다. 형제끼리는 따지지 않습니다.

모양 규칙도 하나 있습니다. 위층부터, 같은 층에서는 왼쪽부터 빈틈없이 채웁니다. 이런 트리를 완전 이진 트리(complete binary tree)라 합니다. 이 모양 덕분에 한쪽으로 치우칠 일이 없고, 위층부터 읽은 순서대로 배열 하나에 담을 수 있습니다.

노드나 칸을 눌러 고릅니다.
13274598106
배열
0123456789
  • 고른 칸: 1번 (3)
  • 부모 (1 − 1) ÷ 2의 몫 = 0번 칸 (1)
  • 왼쪽 자식 2 × 1 + 1 = 3번 칸 (7)
  • 오른쪽 자식 2 × 1 + 2 = 4번 칸 (4)

i번 칸의 왼쪽 자식은 2i + 1번, 오른쪽 자식은 2i + 2번, 부모는 (i − 1) ÷ 2의 몫 번 칸입니다. 이 계산이 포인터 역할을 대신합니다.

넣기와 꺼내기

넣을 때는 새 값을 배열 맨 끝에 둔 뒤, 부모보다 작으면 자리를 바꾸며 올라갑니다. 부모보다 작지 않거나 루트에 닿으면 멈춥니다.

꺼낼 때는 루트를 가져가고, 빈 루트에 배열 맨 끝 값을 옮겨 놓습니다. 이 값은 두 자식 중 더 작은 쪽보다 크면 자리를 바꾸며 내려갑니다.

긴급도 (1~99, 작을수록 급함)
2538769
배열
20513283746596

값을 넣거나 꺼낸 뒤 "다음"으로 한 칸씩 움직여 봅시다.

이번에 자리 바꾼 횟수 0 · 지금 층 수 3
꺼낸 순서
아직 없음
  1. “넣기”를 누른 뒤 “다음”을 눌러 봅시다.
  2. “꺼내기”를 누른 뒤 멈출 때까지 “다음”을 눌러 봅시다.

넣기를 C로 옮기면 다음과 같습니다.

1#include <stdio.h>
2
3int main(void) {
4 int heap[8] = {2, 5, 3, 8, 7, 6, 9};
5 // 담긴 값 수
6 int size = 7;
7 // 맨 끝에 둔다
8 heap[size] = 4;
9 size = size + 1;
10
11 int i = size - 1;
12 while (i > 0) {
13 int parent = (i - 1) / 2;
14 if (heap[parent] <= heap[i]) {
15 break;
16 }
17 // 부모와 자리를 바꾼다
18 int tmp = heap[parent];
19 heap[parent] = heap[i];
20 heap[i] = tmp;
21 i = parent;
22 }
23 for (int k = 0; k < size; k++) {
24 printf("%d ", heap[k]);
25 }
26 printf("\n");
27 return 0;
28}

변수 없음
출력 없음

i는 4가 있는 칸, parent는 그 부모 칸입니다. 맨 끝에 두는 4를 1로 바꿔 봅시다.

자리 바꾸기는 한 층에 한 번뿐입니다. 값이 100만 개여도 20층이면 담기니, 넣거나 꺼낼 때 자리 바꾸기가 많아야 19번입니다.

도전 문제

빈 최소 힙에 1부터 10까지 열 값을 어떤 순서로 하나씩 넣습니다. 넣는 순서에 따라 넣는 동안 일어나는 자리 바꾸기의 총 횟수가 달라집니다. 가장 많을 때 몇 번일까요? 숫자로 답하세요.