힙과 우선순위 큐 - 제일 급한 것만 위로

응급실은 온 순서대로 진료하지 않는다. 먼저 온 사람이 감기고 방금 실려 온 사람이 위독하면 방금 온 쪽이 먼저 들어간다.

온 순서가 아니라 급한 순서

앞에서 본 큐는 먼저 온 것을 먼저 꺼냈다. 공정하지만 모든 일이 그래도 되는 건 아니다.

응급실에서 필요한 건 다른 질문이다. “다음에 볼 사람은 누구인가”, 그러니까 지금 대기 중인 사람 가운데 제일 급한 하나다. 온 순서는 상관없다.

이 질문에 답하는 그릇이 우선순위 큐이고, 그걸 만드는 방법이 힙이다.

꼭대기 하나만 약속한다

여기서 힙이 왜 싼지가 나온다. 힙은 전체를 줄 세우지 않는다.

전체를 줄 세운 게 아니다. 꼭대기 하나만 제일 크고, 나머지는 느슨하게 둔다.

힙이 지키는 약속은 딱 하나다. 어느 자리에서든 자기가 자기 아래쪽보다 급하다. 그게 전부다. 형제끼리 누가 더 급한지는 정해져 있지 않고, 두 단 아래의 것이 옆 가지의 것보다 급할 수도 있다.

그래서 힙을 통째로 훑으면 정렬된 것처럼 안 보인다. 오직 꼭대기 하나만 전체에서 제일 급하다는 게 보장된다.

이게 약점이 아니라 설계다. 우리가 물어보는 건 “다음 한 명”뿐인데 전체를 줄 세우는 건 묻지도 않은 것에 값을 치르는 일이다. 덜 약속하면 그만큼 싸진다.

참고

응급실 비유가 깨지는 자리를 밝혀둔다. 실제 응급실은 사람이 전체를 보고 판단한다. 힙은 그런 관리자가 없다. 각자 자기 바로 아래만 확인하고, 그 지역 규칙이 쌓여서 꼭대기가 저절로 제일 급한 것이 된다. 전체를 보는 눈이 없다는 게 힙이 싼 이유다.

넣기: 올라가며 자리를 찾는다

새 환자가 왔다. 힙은 일단 맨 끝에 붙인다. 그리고 부모와 견줘서 자기가 더 급하면 자리를 맞바꾼다. 안 급해질 때까지 올라간다.

plaintext

넣는다: 급도 9 (숫자가 클수록 급하다)

   8            8            9
  / \          / \          / \
 5   7   →    5   7   →    5   8
/            / \          / \
3           3   9        3   7      ← 두 번 올라가고 멈춤

한 단 오를 때마다 후보가 절반씩 줄어든 그 깊이만큼만 움직인다. 100만 개가 들어 있어도 스무 번쯤이다.

빼기: 내려가며 자리를 찾는다

꼭대기를 꺼내면 자리가 빈다. 여기서 힙은 영리한 짓을 한다. 맨 끝에 있던 것을 꼭대기로 올려놓고 아래로 내려보낸다.

왜 하필 맨 끝인가. 그 자리를 없애는 게 모양을 안 망가뜨리는 유일한 방법이기 때문이다. 올려놓은 것은 대개 안 급하니 자식 중 더 급한 쪽과 바꾸며 제자리까지 내려간다.

넣기도 빼기도 깊이만큼만 움직인다. 꺼내는 값이 O(log n)이라는 게 여기서 나온다. 그런데 **꼭대기를 보기만 하는 것은 O(1)**이다. 그냥 맨 위를 읽으면 된다.

배열 하나로 트리를 담는다

힙은 트리처럼 그리지만 실제로는 배열 하나로 만든다. 포인터가 없다.

plaintext

배열:  [9, 5, 8, 3, 7]
        0  1  2  3  4

0번의 자식은 1번과 2번
1번의 자식은 3번과 4번
n번의 자식은 2n+1번과 2n+2번

부모와 자식이 계산으로 나온다. 앞에서 본 이진탐색트리는 자식이 어디 있는지 주소를 들고 다녀야 했는데, 힙은 중간에 구멍이 안 생기는 모양이라 그럴 필요가 없다.

그래서 힙은 트리의 이점과 배열의 이점을 같이 갖는다. 깊이만큼만 움직이면서도 데이터가 붙어 있어 덩어리째 읽힌다. 앞 글에서 본 “실무에서 배열이 이기는 이유”가 여기에도 그대로 적용된다.

메모리의 힙과는 아무 관계가 없다

이 시리즈 첫 글에서 미리 갈라둔 이름이 여기서 나온다.

	자료구조의 힙	메모리의 힙
무엇인가	꼭대기가 제일 급한 그릇	프로그램이 얻어 쓰는 메모리 영역
쓰는 이유	다음에 처리할 하나를 꺼내려고	오래 살 데이터를 두려고
관계	없다	없다

이름이 겹치는 건 역사적인 우연에 가깝다. 두 낱말은 어원만 같지 서로를 설명하지 않는다. “힙에 할당한다”와 “힙에서 꺼낸다”는 완전히 다른 세계의 문장이다.

실무에서: 전부 정렬하지 않고 상위 N개

힙이 실무에서 값을 하는 대표 자리는 상위 몇 개만 뽑을 때다.

로그 1,000만 줄에서 가장 느린 요청 10개를 찾는다고 하자. 전부 정렬하면 1,000만 개를 줄 세우고 열 개만 쓴다. 999만 9,990개를 정렬한 일은 통째로 버려진다.

전부 정렬한 다음 위에서 10개

1,000만 개를 들고 있어야

1,000만 개를 전부 줄 세우고 앞의 조각만 쓴다. 나머지를 정렬한 일은 버려진다.

크기 10짜리 힙으로 한 번 훑기

10개만

같은 데이터를 한 번 지나가며 그릇 안의 제일 약한 것과만 견준다.

얻는 답은 똑같다. 다른 건 들고 있어야 하는 양과 버리는 일의 양이다.

힙을 쓰면 크기 10짜리 그릇 하나만 들고 한 번 훑으면 된다. 새 값이 그릇 안의 제일 약한 것보다 나으면 바꿔 넣고, 아니면 버린다. 메모리도 열 개분만 든다.

이 모양이 이름을 바꿔가며 여기저기 나온다.

스케줄러 - 다음에 실행할 작업 하나를 고른다. 운영체제도, 잡 스케줄러도 이 구조다.
타임아웃 관리 - 수만 개의 연결에서 “가장 먼저 만료될 것”만 알면 된다. 전부 정렬할 이유가 없다.
정렬된 목록 여러 개 합치기 - 각 목록의 첫 값만 힙에 넣고 하나씩 꺼내면 전체가 정렬되어 나온다. 여러 서버에서 온 결과를 시간순으로 합칠 때 쓰는 방법이 이거다.

라이브러리에서는 대개 PriorityQueue라는 이름으로 있다. 직접 만들 일은 드물고, “정렬하려던 것이 사실 상위 N개 문제가 아닌지” 알아보는 게 실무의 쓸모다.

정리

힙은 꼭대기 하나만 약속한다. 형제끼리 누가 급한지는 정해두지 않는다.
덜 약속해서 싸다. 묻는 것이 “다음 하나”뿐인데 전체를 줄 세우는 건 낭비다.
넣기도 빼기도 깊이만큼만 움직이고, 꼭대기를 보기만 하는 것은 공짜다.
배열 하나로 만든다. 부모와 자식이 계산으로 나와서 포인터가 없다.
메모리의 힙과는 아무 관계가 없다. 이름만 같다.
실무의 쓸모는 전부 정렬하지 않고 상위 N개를 뽑는 자리다.

다음 글은 지금까지와 담는 것 자체가 다르다. 값이 아니라 값들 사이의 관계가 데이터인 경우다.