힙 (Heap)
최댓값/최솟값을 O(1)에 찾고 O(log N)에 삽입/삭제하는 완전 이진 트리
종류
[최소 힙] 부모 <= 자식
1
/ \
3 2
/ \
7 4
[최대 힙] 부모 >= 자식
9
/ \
7 8
/ \
3 5
시간 복잡도
| 연산 | 복잡도 |
|---|
| 최솟값/최댓값 조회 | O(1) |
| 삽입 | O(log N) |
| 삭제 (루트) | O(log N) |
| 힙 생성 | O(N) |
삽입 과정 (최소 힙)
2를 삽입:
1 1
/ \ → / \
3 5 3 2 ← 부모와 교환
/ / \
2→추가 7 5
1) 맨 끝에 추가
2) 부모와 비교하며 올라감 (bubble up)
삭제 과정 (루트 제거)
1 7 2
/ \ → / \ → / \
2 3 2 3 7 3
/
7
1) 루트 제거, 마지막 노드를 루트로
2) 자식과 비교하며 내려감 (bubble down)
배열로 구현
배열 [1, 3, 2, 7, 4] 를 완전 이진 트리로 본 것입니다.
0번이 뿌리이고, 1번과 2번이 그 자식, 3번과 4번이 1번의 자식입니다.
| 관계 | 계산 |
|---|
| 부모 | (i - 1) / 2 |
| 왼쪽 자식 | 2i + 1 |
| 오른쪽 자식 | 2i + 2 |
우선순위 큐
힙 = 우선순위 큐의 대표 구현
일반 큐: FIFO (선입선출)
우선순위 큐: 우선순위 높은 것 먼저!
활용:
- 작업 스케줄링 (우선순위별)
- 다익스트라 최단경로
- 허프만 코딩 (압축)
- 이벤트 시뮬레이션
힙 정렬
1) 최대 힙 구성: O(N)
2) 루트(최댓값)를 꺼내서 뒤에 배치
3) 힙 재구성
4) 반복 → O(N log N) 정렬
| 비교 | 힙 정렬 | 퀵 정렬 |
|---|
| 시간 | O(N log N) | O(N log N) 평균 |
| 최악 | O(N log N) | O(N²) |
| 공간 | O(1) | O(log N) |
| 안정성 | 불안정 | 불안정 |
| 캐시 | 나쁨 | 좋음 |