"가장 작은 것만 계속 필요하다면 전부를 정렬하는 건 낭비야. 힙은 가장 작은 걸 맨 위에 두기에 딱 필요한 만큼만 정렬하고, 아낀 만큼을 그대로 챙겨."
핵심 깨달음
작업이 백만 개 있고 늘 가장 급한 걸 먼저 잡는다고 해 보자. 백만 개를 다 정렬해야 할까? 아니야. 매 순간 가장 급한 하나만 알면 돼. 그런데 완전히 정렬된 리스트를 유지하려면 삽입할 때마다 O(n)이 들어. 한참 뒤에나 볼 작업까지 줄 세우느라 값을 치르는 거지. 힙은 이렇게 말하는 구조야. 문제가 요구하는 만큼만 정렬해.
힙 속성
최소 힙은 힙 속성이라는 규칙 하나만 따라. 모든 부모가 자식보다 작거나 같다. 규칙은 이 한 줄이고, 위에서 아래로 모든 노드에 적용돼. 정렬에 비하면 얼마나 느슨한지 봐. 형제끼리의 순서에 대해서도, 다른 서브트리에 있는 사촌끼리에 대해서도 아무 말을 안 해. 같은 원소로 만든 힙 두 개가 완전히 다르게 생길 수도 있어. 그런데 이 규칙 하나가 정말 중요한 걸 보장해. 최솟값이 언제나 루트에 있다는 것. 어떤 노드도 자기 부모보다 작지 않으니까 위로 쭉 올라가면 그렇게 되거든. 최대 힙은 규칙을 뒤집어서 부모가 자식보다 크거나 같고, 그래서 최댓값이 맨 위에 오고.
힙 속성은 최소 힙 기준으로 모든 부모가 자식보다 작거나 같다는 거야. 완전 정렬보다 훨씬 약해서 형제끼리는 순서가 없지만, 최솟값을 루트에 붙들어 두기에는 충분히 강해. '게으른 정렬'이라고 봐도 돼. 실제로 쓸 만큼의 순서에만 값을 치르는 거니까.
정렬이 아니라 '필요한 만큼만'
여기가 핵심이고 다른 데도 통하는 교훈이야. 힙은 부분적으로만 정렬돼 있고, 그 부분 순서는 던진 질문에 답하면서도 가장 싼 수준으로 일부러 맞춰져 있어. 정렬된 리스트는 "전부 순서대로 줘"에 답하지만 유지 비용이 커. 힙은 "극값만 줘"에만 답해. 더 약한 약속이니까 유지가 훨씬 싸지. 삽입이 O(n)이 아니라 O(log n)이야. 해시맵은 순서를 아예 안 주고 정렬된 리스트는 너무 많이 줄 때, 힙이 정확히 그 중간에 있어. 꼭대기만, 싸게, 언제나.
피파의 고백
작업 큐에 완전히 정렬된 리스트를 유지하면서 삽입할 때마다 다시 정렬했고, 왜 이렇게 기어가나 싶었어. 아빠가 질문 하나를 던지더라. "맨 앞 말고 다른 거 본 적 있어?" 없었어. 늘 가장 급한 것만 꺼내 썼거든. 하나 읽으려고 천 개를 줄 세우는 값을 치르고 있었던 거야. 힙은 자료구조를 넘어서는 원칙을 하나 가르쳐 줬어. 문제가 실제로 요구하는 것보다 더 많은 순서를 계산하지 말 것. 내 코드에서도 맞는 말이었고, 창피할 만큼 자주 내 삶에서도 맞는 말이었어.
Code
유효한 힙은 정렬된 배열이 아니야·python
# 최소-힙을 배열로. 부모 i, 자식 2i+1 이랑 2i+2.
heap = [1, 3, 2, 7, 4, 9, 5]
# 1
# / \
# 3 2
# / \ / \
# 7 4 9 5
def is_min_heap(a):
"""힙 속성 확인: 모든 부모 <= 자식."""
for i in range(len(a)):
left, right = 2 * i + 1, 2 * i + 2
if left < len(a) and a[i] > a[left]: return False
if right < len(a) and a[i] > a[right]: return False
return True
print("valid heap? ", is_min_heap(heap)) # True
print("min (root): ", heap[0]) # 1 — 인덱스 0 에 보장됨
print("is it sorted?", heap == sorted(heap)) # False! [1,3,2,7,4,9,5] != 정렬
# 결정적: 배열은 정렬 안 됐는데, 최솟값은 안정적으로 맨 앞에 있어.
# 그게 '정렬-충분히': 약한 순서지만, 가장 작은 게 늘 위에.
배열 [2, 5, 3, 8, 6, 4]가 유효한 최소 힙일까? 부모마다 부모 ≤ 자식이 성립하는지 확인해 봐. 그다음 답해 봐. 배열이 정렬돼 있지도 않은데 왜 최솟값은 인덱스 0에서 안정적으로 읽을 수 있고, 그 느슨한 보장이 왜 오히려 성능상 이득일까?
Hint
인덱스 0의 부모 2는 5, 3보다 작고, 인덱스 1의 부모 5는 8, 6보다 작고, 인덱스 2의 부모 3은 4보다 작아. 전부 성립하니 유효한 힙이야. 루트는 아래 모든 값보다 작거나 같아서 최솟값이 되고, 그 관계가 아래로 계속 이어지니까 그렇지. 완전한 순서가 아니라 이것만 유지하니까 삽입이 O(n)이 아니라 O(log n)인 거야.
Progress
Progress is local-only — sign in to sync across devices.