한양과기고 에듀테크 수업도구 대시보드

힙 & 우선순위 큐 — 항상 "가장 급한 것"을 먼저

병원 응급실은 온 순서가 아니라 위급한 순서로 환자를 본다. 이렇게 "우선순위가 가장 높은 것을 빠르게 꺼내는" 자료구조가 우선순위 큐(priority queue)이고, 그걸 효율적으로 구현하는 방법이 힙(heap)이다. 힙은 완전 이진 트리를 배열 하나로 표현하며, 삽입·삭제가 모두 O(log n)이다. 다익스트라 최단경로, 허프만 코딩, 작업 스케줄러, 이벤트 시뮬레이션에서 쓰인다.

1. 힙의 두 가지 규칙

① 힙 순서 (heap property)

최소 힙이면 모든 부모는 자식보다 작거나 같다. 그래서 트리 전체에서 가장 작은 값은 항상 맨 위(뿌리, 배열 0번)에 있다. 형제끼리는 순서가 없어도 된다 — 정렬된 트리가 아니다.

② 완전 이진 트리 (shape)

위에서 아래로, 왼쪽에서 오른쪽으로 빈틈없이 채워진다. 덕분에 포인터 없이 배열로 담아도 구멍이 안 생기고, 부모·자식 위치를 인덱스 계산만으로 찾을 수 있다.

2. 직접 넣고 빼 보기

배열 표현 (트리를 위에서 아래로 훑은 순서):

숫자를 넣고 삽입을 눌러보세요. 새 값은 맨 끝에 붙은 뒤 제자리로 떠오릅니다(sift-up).

3. 배열로 부모·자식 찾기

0번부터 시작하는 배열에서, i번 노드의 이웃은 이렇게 구한다. 포인터도, 추가 메모리도 필요 없다.

부모 (parent)(i - 1) / 2

왼쪽 자식 (left)2·i + 1

오른쪽 자식 (right)2·i + 2

예) 인덱스 3의 부모 = (3−1)/2 = 1, 자식 = 7·8. 자식 인덱스가 배열 길이를 넘으면 자식이 없는 것이다.

4. 핵심 연산 (의사코드)

# 삽입: 맨 끝에 넣고, 부모보다 작으면 부모와 자리 바꾸며 위로 def push(heap, x): heap.append(x) i = len(heap) - 1 while i > 0 and heap[(i - 1) // 2] > heap[i]: # 최소 힙 swap(heap, i, (i - 1) // 2) i = (i - 1) // 2 # 삭제: 뿌리를 꺼내고, 마지막 값을 뿌리에 올린 뒤 아래로 가라앉힘 def pop(heap): top = heap[0] heap[0] = heap.pop() # 마지막 원소를 뿌리로 i = 0 while True: smallest, l, r = i, 2*i + 1, 2*i + 2 if l < len(heap) and heap[l] < heap[smallest]: smallest = l if r < len(heap) and heap[r] < heap[smallest]: smallest = r if smallest == i: break swap(heap, i, smallest); i = smallest return top # 파이썬에는 heapq 모듈이 이미 있다 import heapq heapq.heappush(pq, 5); heapq.heappop(pq)

5. 시간 복잡도

연산	힙	정렬된 배열	그냥 배열
최솟값 확인	O(1)	O(1)	O(n)
삽입	O(log n)	O(n)	O(1)
최솟값 제거	O(log n)	O(1)	O(n)
n개로 힙 만들기	O(n)	O(n log n)	O(n)

트리 높이가 log₂ n이라서, sift-up·sift-down은 최악에도 한 층씩 높이만큼만 이동한다.

6. 힙이 쓰이는 곳

다익스트라 최단 경로

"아직 확정 안 된 정점 중 가장 가까운 것"을 매번 꺼내야 한다. 우선순위 큐로 O(E log V).

허프만 코딩

빈도가 가장 작은 노드 둘을 반복해서 꺼내 합친다. 최소 힙이 딱 맞는다.

힙 정렬 (Heapsort)

전부 넣고 하나씩 꺼내면 정렬된다. O(n log n), 추가 메모리 없이 제자리 정렬.

Top-K

수백만 개 중 상위 10개만 필요할 때, 크기 10짜리 힙만 유지하면 전체 정렬이 필요 없다.

이진 힙은 1964년 J. W. J. Williams가 힙 정렬과 함께 발표했다.