이 Part에서 다루는 것
- 우선순위 큐가 필요한 문제 패턴(정렬/선형 탐색과 비교)
- 힙의 2가지 핵심 법칙(힙 속성 + 완전 이진트리)
Push/Pop동작 원리와 시간 복잡도- C++ STL에서 최소 힙/커스텀 우선순위 설정 방법
- A*·다익스트라에서 우선순위 큐가 성능을 바꾸는 이유
학습 목표
- “왜 힙을 쓰는지”를 복잡도 근거로 설명할 수 있다.
- 최대 힙/최소 힙 동작을 배열 인덱스로 직접 추적할 수 있다.
- 실전 코드에서 우선순위 큐 관련 흔한 실수를 피할 수 있다.
왜 필요한가
문제 상황
- 데이터가 계속 바뀌는 상황에서 최댓값/최솟값 1개를 반복적으로 꺼내야 합니다.
- 예: 길찾기 오픈 리스트(A*), 최단거리 후보(다익스트라), 작업 스케줄링, 이벤트 처리.
- 매번 정렬하면
O(N log N), 매번 스캔하면O(N)이 듭니다. - 우선순위 큐는
Push/Pop을O(log N),Top을O(1)로 처리합니다.
핵심 관점
- 우선순위 큐는 “전체 정렬”이 아니라 “맨 위 원소 보장”에 최적화된 구조입니다.
- 즉, 모든 원소의 순서는 몰라도 지금 당장 필요한 1개를 빠르게 꺼낼 수 있습니다.
혼동 주의
- 자료구조의 힙(Heap): 우선순위 큐를 구현하는 완전 이진트리 기반 구조
- 메모리 힙(Heap Memory): 동적 할당 영역 (
new,malloc) - 면접에서 “힙”이라고 하면 맥락(자료구조 vs 메모리)을 먼저 구분해야 합니다.
힙 트리 법칙
힙 속성(Heap Property)
- 최대 힙: 부모 값 >= 자식 값
- 최소 힙: 부모 값 <= 자식 값
- 좌/우 자식의 상대 순서는 중요하지 않습니다.
완전 이진트리(Complete Binary Tree)
- 마지막 레벨 전까지는 노드가 모두 채워져 있습니다.
- 마지막 레벨은 왼쪽부터 채워집니다.
- 이 성질 덕분에 포인터 트리 없이 배열 인덱스만으로 구조를 복원할 수 있습니다.
배열 인덱스 공식(0-based)
인덱스 i 기준:
| 관계 | 공식 |
|---|---|
| 왼쪽 자식 | 2*i + 1 |
| 오른쪽 자식 | 2*i + 2 |
부모 (i > 0) | (i - 1) / 2 |
- 실제 구현은
vector<T>가 가장 일반적입니다. - 힙 높이는
log N이므로 위/아래 이동 비용도O(log N)입니다.
예시로 감각 잡기(최대 힙)
배열: [50, 30, 40, 10, 20, 35]
50
/ \
30 40
/ \ /
10 20 35- 형제끼리(
30,40) 누가 큰지는 상관없습니다. - 부모-자식 관계만 법칙을 만족하면 됩니다.
Push (삽입, Sift Up)
맨 뒤에 삽입
- 완전 이진트리 규칙을 지키려면 새 원소는 항상 배열 끝에 들어갑니다.
위로 올리기
- 새 원소가 부모보다 크면(최대 힙 기준) 부모와 스왑합니다.
- 루트에 도달하거나 부모가 더 크거나 같아질 때까지 반복합니다.
- 이 과정을
Sift Up(또는Heapify Up)이라고 합니다.
예시:
초기: [50, 30, 40, 10, 20, 35]
45 삽입: [50, 30, 40, 10, 20, 35, 45]
부모(40)와 스왑: [50, 30, 45, 10, 20, 35, 40]
종료(부모 50 >= 45)Pop (최댓값 제거, Sift Down)
루트 제거 후 마지막 원소 이동
- 최댓값은 루트(
index 0)에 있으므로 먼저 제거합니다. - 배열 마지막 원소를 루트로 옮겨 빈자리를 메웁니다.
아래로 내리기
- 두 자식 중 더 큰 자식과 비교해 필요하면 스왑합니다(최대 힙).
- 리프에 도달하거나 법칙을 만족하면 중단합니다.
- 이 과정을
Sift Down(또는Heapify Down)이라고 합니다.
예시:
초기: [50, 30, 45, 10, 20, 35, 40]
50 제거 + 40 이동: [40, 30, 45, 10, 20, 35]
더 큰 자식(45)와 스왑: [45, 30, 40, 10, 20, 35]
종료(40 >= 35)시간 복잡도
| 연산 | 복잡도 | 이유 |
|---|---|---|
Push | O(log N) | 트리 높이만큼 위로 이동 |
Pop | O(log N) | 트리 높이만큼 아래로 이동 |
Top | O(1) | 루트(인덱스 0) 접근 |
Build Heap | O(N) | 바닥부터 Heapify할 때 선형 시간 |
면접 포인트:
- “왜
Push/Pop이log N인가?” -> 힙 높이가log N이기 때문 - “왜
Build Heap은N log N이 아니라N인가?” -> 아래 레벨 노드는 이동 거리가 짧아 총합이 선형
최소값 먼저 꺼내기 (Min-Heap)
음수 트릭 (권장도 낮음)
- 값을 음수로 넣고 꺼낼 때 다시 부호를 바꾸는 방식
- 정수 오버플로우 위험이 있고, 가독성이 떨어지며, 숫자가 아닌 타입에는 적용하기 어렵습니다.
비교자 사용 (권장)
std::priority_queue<int, std::vector<int>, std::greater<int>> minPQ;- STL
priority_queue기본은 최대 힙입니다. - 최소 힙이 필요하면
greater<>또는 커스텀 비교자를 사용하세요.
A*·다익스트라와의 관계
- 두 알고리즘 모두 “현재 비용이 가장 작은 후보”를 반복적으로 꺼냅니다.
- 이 동작이 우선순위 큐와 정확히 맞물립니다.
복잡도 관점:
- 우선순위 큐 없이 벡터/리스트로 최소 후보를 찾으면, 선택마다
O(N)탐색이 필요합니다. - 우선순위 큐를 쓰면 선택/갱신이
O(log N)으로 줄어 대규모 맵에서 체감 성능 차이가 크게 납니다.
실전 구현 팁(C++):
std::priority_queue는 decrease-key를 직접 지원하지 않습니다.- 더 좋은 비용을 찾으면 새 항목을 다시
push하고,pop시 최신 거리와 다르면 버리는 방식(지연 삭제)을 사용합니다.
자주 하는 실수 + 체크 질문
자주 하는 실수
| 실수 | 문제 |
|---|---|
빈 큐에서 top()/pop() 호출 | 런타임 오류 위험 |
최소 힙인데 기본 priority_queue 사용 | 정반대 순서로 동작 |
Sift Down에서 더 작은 자식과 스왑 | 힙 속성 깨짐 |
| “힙 = 완전 정렬”로 오해 | Top 외 순서에 잘못 의존 |
| 음수 트릭 남용 | 오버플로우/가독성 저하 |
체크 질문 (스스로 답해보기)
- 왜 힙은
Top이O(1)인데Push/Pop은O(log N)일까? - 힙을 배열로 구현할 수 있는 핵심 전제는 무엇일까?
- 다익스트라에서 우선순위 큐를 빼면 어떤 연산이 병목이 될까?
- 최소 힙을 C++ STL로 만들 때 가장 안전한 선언은 무엇일까?
李家네_공부방