thenullpage.com
1. 가장 작은 값만 계속 꺼내야 할 때
줄을 선 순서대로 처리하는 일이 있고 급한 것부터 처리하는 일이 있습니다. 은행 창구는 앞사람부터지만 응급실은 위중한 환자부터입니다. 뒤쪽 같은 상황에서는 값이 계속 들어오는 중에도 그때그때 가장 작은 값을 꺼낼 수 있어야 합니다.
리스트로도 됩니다. 매번 최솟값을 찾아서 지우면 됩니다.
box = [5, 3, 8, 1, 9, 2]
order = []
while box:
smallest = min(box)
box.remove(smallest)
order.append(smallest)
print(order)
[1, 2, 3, 5, 8, 9]
결과는 맞지만 min이 리스트를 한 번 훑고 remove가 또 한 번 훑습니다. 하나 꺼내는 데 O(n)이고 전부 꺼내면 O(n^2)입니다. 미리 정렬해 두는 방법도 있는데, 값이 중간에 새로 들어올 때마다 자리를 찾아 끼워 넣어야 해서 그 비용이 다시 O(n)입니다. 필요한 것은 전부 줄 세우는 일이 아니라 가장 작은 값 하나뿐이고, 딱 그 일만 잘하는 구조가 힙(heap)입니다.
2. 부모가 자식보다 작다는 약속 하나
힙도 이진 트리지만 규칙이 헐겁습니다. 왼쪽인지 오른쪽인지는 따지지 않고 부모가 두 자식보다 작기만 하면 되며, 이것을 최소 힙이라고 합니다. 형제끼리는 누가 크든 상관없습니다. 대신 위층부터 왼쪽에서 오른쪽으로 빈칸 없이 채운 모양은 지킵니다.
파이썬은 heapq 모듈이 리스트를 힙으로 다뤄 줍니다.
import heapq
nums = [5, 3, 8, 1, 9, 2, 7]
heapq.heapify(nums)
print(nums)
print(nums[0])
[1, 3, 2, 5, 9, 8, 7]
1
정렬된 것이 아닙니다. 3이 2보다 앞에 있습니다. 트리로 읽으면 1 아래에 3과 2가, 3 아래에 5와 9가, 2 아래에 8과 7이 있어서 부모마다 자식보다 작다는 조건만 지켜집니다. 규칙이 이만큼 느슨하니 값을 넣거나 뺄 때 건드리는 범위가 좁고, 대신 맨 앞이 최솟값이라는 것 말고는 아무것도 보장하지 않습니다. heapify는 리스트 전체를 O(n)에 이 모양으로 바꿉니다.
3. 트리를 배열 하나에 담습니다
빈칸 없이 채운다는 조건 덕분에 노드 클래스도 연결도 필요 없습니다. 위층부터 순서대로 배열에 넣으면 자리 계산만으로 부모와 자식을 찾을 수 있습니다.
heap = [1, 3, 2, 5, 9, 8, 7]
for i in range(3):
print(heap[i], heap[2 * i + 1], heap[2 * i + 2])
1 3 2
3 5 9
2 8 7
i번 자리의 두 자식은 2i+1과 2i+2이고, 거꾸로 자식에서 부모로 올라갈 때는 (i-1)//2입니다. 5번 자리에 있는 8의 부모는 (5-1)//2인 2번 자리의 2입니다. 트리라고 해서 반드시 노드를 만들어 이어 붙일 필요는 없다는 것을 힙이 보여 줍니다.
4. 넣을 때는 올라가고 꺼낼 때는 내려갑니다
heappush로 하나씩 넣으면서 리스트가 어떻게 변하는지 찍어 보겠습니다.
h = []
for v in [5, 3, 8, 1]:
heapq.heappush(h, v)
print(v, h)
print(heapq.heappop(h), h)
5 [5]
3 [3, 5]
8 [3, 5, 8]
1 [1, 3, 8, 5]
1 [3, 5, 8]
새 값은 일단 맨 뒤에 붙습니다. 그다음 부모와 비교해서 자기가 더 작으면 자리를 바꾸며 위로 올라갑니다. 1을 넣었을 때 [3, 5, 8, 1]이 아니라 [1, 3, 8, 5]가 된 것이 그 과정입니다. 꺼낼 때는 반대로 맨 앞을 빼내고 마지막 값을 그 자리에 올린 다음 더 작은 자식과 바꾸며 내려갑니다. 어느 쪽이든 한 층씩만 움직이니 비용은 층수에 비례하는 O(log n)입니다. 꺼내지 않고 최솟값만 보고 싶으면 h[0]을 읽으면 되고 이것은 O(1)입니다.
5. 최대 힙과 우선순위 붙이기
파이썬 heapq에는 최소 힙만 있습니다. 가장 큰 값을 꺼내야 하면 부호를 뒤집어 넣고 꺼낼 때 다시 뒤집습니다.
mh = [-v for v in [5, 3, 8, 1, 9, 2]]
heapq.heapify(mh)
print(-heapq.heappop(mh), -heapq.heappop(mh))
9 8
값이 아닌 다른 기준으로 순서를 정하고 싶으면 튜플을 넣습니다. 튜플은 앞자리부터 비교하므로 첫 번째 칸에 우선순위를 두면 됩니다.
tasks = [(3, "보고서"), (1, "서버 점검"), (2, "회의 준비")]
heapq.heapify(tasks)
while tasks:
print(heapq.heappop(tasks))
(1, '서버 점검')
(2, '회의 준비')
(3, '보고서')
넣은 순서와 상관없이 숫자가 작은 것부터 나옵니다. 이렇게 순서를 매겨 꺼내는 큐를 우선순위 큐(priority queue)라고 하고, 힙은 그것을 만드는 가장 흔한 재료입니다. 다만 우선순위가 같으면 두 번째 칸을 비교하므로, 서로 비교할 수 없는 객체를 두 번째에 넣어 두면 그 순간 TypeError가 납니다.
6. 큰 값 몇 개만 남기기
점수가 아주 많은데 큰 순서로 세 개만 필요한 경우를 보겠습니다. 전부 정렬하면 O(n log n)이지만, 크기 3짜리 최소 힙을 유지하면 더 적게 씁니다.
scores = [42, 91, 17, 88, 63, 75, 30]
top = []
for s in scores:
heapq.heappush(top, s)
if len(top) > 3:
heapq.heappop(top)
print(sorted(top, reverse=True))
[91, 88, 75]
힙에 넣고 넘치면 하나 버리는데, 최소 힙이라 버려지는 것은 늘 그 안에서 가장 작은 값입니다. 그래서 큰 값 세 개만 남습니다. 힙 크기가 k로 고정되니 비용은 O(n log k)이고, 데이터가 많고 k가 작을수록 정렬과 차이가 벌어집니다.
7. 힙은 정렬된 상태가 아닙니다
가장 흔한 오해가 힙을 정렬된 배열처럼 여기는 것입니다.
x = [5, 3, 8, 1, 9, 2, 7]
heapq.heapify(x)
print(x.index(7))
print(sorted(x))
6
[1, 2, 3, 5, 7, 8, 9]
7은 6번 자리에 있는데 이 위치를 계산으로 알아낼 방법이 없습니다. 힙에서 특정 값을 찾는 일은 결국 전부 뒤지는 O(n)입니다. 두 번째로 작은 값을 x[1]에서 읽으려는 코드도 자주 보이는데, 위 힙에서 x[1]은 3이지만 두 번째로 작은 값은 2입니다. 정렬된 결과가 필요하면 sorted를 따로 불러야 하고, 힙을 앞에서부터 읽으면 순서가 뒤섞여 나옵니다. 힙이 싸게 답해 주는 질문은 지금 가장 작은 값이 무엇이냐 하나뿐입니다.
8. 챙길 것
힙은 전부 줄 세우는 일을 포기하는 대신 맨 앞 하나를 싸게 얻는 구조입니다.
기억할 것은 세 가지입니다. 부모가 자식보다 작다는 조건만 지키고 형제 사이 순서는 보장하지 않는다는 것, 빈칸 없는 모양 덕분에 배열 하나로 구현되고 넣기와 꺼내기가 O(log n), 맨 앞 확인이 O(1)이라는 것, 그리고 힙은 정렬이 아니라서 특정 값을 찾는 일에는 맞지 않는다는 것입니다.