힙(heap)은 "가장 작은 값(또는 가장 큰 값)을 항상 빠르게 꺼낼 수 있는" 트리 기반 자료구조입니다. 값을 아무 순서로 넣어도, 꺼낼 때는 늘 가장 작은 것이 먼저 나옵니다. 파이썬은 heapq(힙큐)라는 표준 모듈로 평범한 리스트를 최소 힙처럼 다룹니다. 힙은 "중요한 것부터 처리하라"는 우선순위 큐(priority queue)의 핵심이라, 작업 스케줄러나 최단 경로 찾기 같은 실전 문제에서 널리 쓰입니다. 하나씩 실행해 보겠습니다.
12.1 넣고 꺼내면 항상 최소가 먼저
힙에 값을 넣을 때는 heappush, 뺄 때는 heappop을 씁니다. 빈 리스트를 하나 만들어 두고 이 함수들에 넘기면 됩니다. 어떤 순서로 넣든 heappop은 항상 가장 작은 값을 돌려줍니다.
import heapq
h = []
for x in [5, 1, 8, 3]:
heapq.heappush(h, x)
print(h) # 내부 리스트(완전한 정렬 아님)
print(heapq.heappop(h)) # 최소값
print(h)
[1, 3, 8, 5]
1
[3, 5, 8]
넣고 나서 리스트를 출력하니 [1, 3, 8, 5]입니다. 완전히 정렬된 상태는 아니지만, 맨 앞(인덱스 0)만은 언제나 가장 작은 값이 오도록 힙이 자리를 정리해 둡니다. 그래서 heappop을 하면 최소값 1이 빠지고, 남은 값들이 다시 정리되어 맨 앞에 3이 옵니다. 넣기와 빼기 모두 O(log n)으로 빠릅니다.
힙이 완전히 정렬돼 있지 않은데도 최소값을 즉시 아는 비결은 그 속 모양에 있습니다. 힙은 리스트로 표현되지만 머릿속으로는 부모가 자식보다 항상 작거나 같은 트리라고 보면 됩니다. 이 규칙만 지키면 꼭대기(맨 앞)에는 늘 가장 작은 값이 올 수밖에 없습니다. 값을 넣거나 뺄 때는 이 규칙이 깨진 부분만 위아래로 조금씩 자리를 바꿔 고치는데, 트리의 높이가 log n 정도라서 그 수고가 O(log n)에 그칩니다. 전체를 완벽히 줄 세우는 O(n log n) 정렬보다 가볍게, 필요한 "가장 작은 하나"만 빠르게 얻는 것이 힙의 이점입니다.
12.2 리스트를 한 번에 힙으로 바꾸기
이미 값이 들어 있는 리스트가 있다면, 하나씩 push하지 않고 heapify로 한 번에 힙 구조로 바꿀 수 있습니다.
import heapq
data = [9, 4, 7, 1, 2]
heapq.heapify(data)
print(data)
[1, 2, 7, 4, 9]
heapify는 리스트 전체를 훑어 힙 규칙에 맞게 자리를 바꿉니다. 결과를 보면 맨 앞이 가장 작은 값 1이 되었습니다. 하나씩 push하면 O(n log n)이 들지만, heapify는 O(n)에 끝나므로 이미 모아 둔 데이터를 힙으로 만들 때는 heapify가 더 빠릅니다.
12.3 가장 큰 값을 먼저 꺼내고 싶다면
heapq는 최소 힙만 제공합니다. 그런데 가장 큰 값을 먼저 꺼내고 싶을 때가 있습니다. 이럴 때 자주 쓰는 방법이 부호를 뒤집어 넣는 것입니다. 넣을 때 음수로 바꿔 넣으면, 가장 작은 음수가 곧 원래 가장 큰 값이 됩니다.
import heapq
maxh = []
for x in [5, 1, 8, 3]:
heapq.heappush(maxh, -x) # 부호 반대로 넣기
print(-heapq.heappop(maxh)) # 꺼낼 때 다시 반대로
8
5, 1, 8, 3을 각각 음수로 바꿔 넣으면 힙 안에는 -8이 가장 작은 값으로 들어갑니다. heappop으로 -8을 꺼낸 뒤 다시 부호를 뒤집으면 원래 가장 큰 값 8이 됩니다. 간단한 요령이지만 실전에서 자주 등장하니 익혀 두면 좋습니다. 값이 숫자가 아니라 점수나 거리처럼 크기를 비교할 수 있는 것이면 무엇이든 이 방법이 통합니다.
12.4 상위 몇 개만 뽑기
전체를 정렬하지 않고 "가장 큰 몇 개"만 필요할 때가 많습니다. heapq는 이를 위한 nlargest 함수를 제공합니다. 반대로 가장 작은 몇 개를 뽑는 nsmallest도 있습니다.
import heapq
print(heapq.nlargest(3, [5, 1, 8, 3, 9, 2]))
[9, 8, 5]
여섯 개의 점수에서 상위 세 개인 9, 8, 5가 큰 순서로 나왔습니다. 전부 정렬한 뒤 앞에서 세 개를 자를 수도 있지만, nlargest는 힙을 이용해 상위 k개만 효율적으로 추립니다. 뽑을 개수 k가 전체 n보다 훨씬 작을 때 특히 유리하며, 비용은 O(n log k)입니다. 예를 들어 백만 개의 기록에서 상위 열 개만 필요하다면, 전부 정렬하는 것보다 nlargest가 훨씬 가볍게 끝납니다.
12.5 작업 우선순위 큐 만들기
힙의 대표적인 실전 쓰임이 우선순위 큐입니다. (우선순위, 작업) 형태의 튜플을 넣으면, 힙은 튜플의 첫 번째 값을 기준으로 비교하므로 우선순위가 낮은 숫자, 즉 가장 급한 일이 먼저 나옵니다.
import heapq
tasks = []
heapq.heappush(tasks, (2, "청소"))
heapq.heappush(tasks, (1, "긴급버그"))
heapq.heappush(tasks, (3, "문서작성"))
print(heapq.heappop(tasks))
(1, '긴급버그')
청소, 긴급버그, 문서작성을 뒤섞인 순서로 넣었지만, heappop은 우선순위 숫자가 가장 작은 (1, '긴급버그')를 먼저 꺼냈습니다. 숫자가 작을수록 급한 일이라고 정하면, 넣는 순서와 상관없이 늘 가장 급한 일부터 처리됩니다. 이 구조가 바로 운영체제의 작업 스케줄러나 지도 앱의 최단 경로 계산(다익스트라 알고리즘)에서 쓰이는 우선순위 큐입니다. 넣기와 빼기 모두 O(log n)입니다.
만약 이것을 리스트로 흉내 낸다면, 새 작업이 들어올 때마다 전체를 다시 정렬하거나(O(n log n)) 가장 급한 것을 찾으려고 매번 전부 훑어야(O(n)) 합니다. 작업이 수시로 들어오고 나가는 상황에서는 이 비용이 금세 무거워집니다. 힙을 쓰면 넣기도 빼기도 O(log n)에 끝나므로, 급한 일이 끊임없이 밀려드는 서버 같은 곳에서 특히 진가를 발휘합니다. 우선순위를 정하는 첫 번째 값만 잘 설계하면, 나머지는 heapq가 알아서 순서를 지켜 줍니다.
12.6 정리
힙은 가장 작은 값을 항상 O(log n)에 꺼낼 수 있는 구조이고, 파이썬에서는 heapq 모듈로 리스트를 힙처럼 다룹니다. heappush와 heappop으로 넣고 빼며, heapify로 리스트를 한 번에 힙으로 만들고, 부호를 뒤집으면 최대 힙처럼, nlargest로는 상위 몇 개만 뽑습니다. (우선순위, 값) 튜플을 넣으면 우선순위 큐가 되어 급한 일부터 처리합니다. "전체 정렬은 필요 없고 가장 작은(또는 큰) 것 하나만 자주 꺼내면 될 때" 힙이 가장 알맞은 선택입니다. 오늘 예제들을 직접 쳐 보며 값을 넣는 순서를 바꿔도 결과가 같은지 확인해 보시기 바랍니다.