코드를 읽고 설명하면, 합격합니다
이 레슨과 관련된 학습 키워드
자료구조 — 효율적인 데이터 관리의 핵심 → 트리와 그래프
Min-Heap: Max-Heap:
1 9
/ \ / \
3 5 7 8
/ \ / \
7 9 3 5
핵심 특성:
- 완전 이진 트리: 마지막 레벨 제외 모두 채워짐, 왼쪽부터 채움
- 부분 순서: 부모-자식 관계만 보장 (형제 간 순서 없음)
- 높이: 항상 O(log n) — 완전 이진 트리이므로
BST와 차이:
| | BST | Heap |
|--|-----|------|
| 순서 | left < parent < right | 부모 ≤(≥) 자식 |
| 최솟값 | 가장 왼쪽 O(log n) | 루트 O(1) |
| 검색 | O(log n) | O(n) |
| 용도 | 검색/정렬 | 최솟/최댓값 추출 |안녕하세요, 오늘은 힙이라는 특별한 자료구조를 배워볼게요.
그림을 보면 왼쪽에 최소 힙, 오른쪽에 최대 힙이 나란히 있어요.
힙은 완전 이진 트리인데, 여기에 부모-자식 간 순서 규칙이 추가된 거예요.
최소 힙에서는 부모가 항상 자식보다 작거나 같아요.
그래서 왼쪽 트리 꼭대기, 루트를 보면 가장 작은 값 1이 있죠.
반대로 최대 힙은 부모가 자식보다 크거나 같아서 루트가 10이에요.
중요한 건 형제끼리는 순서가 없다는 거예요.
왼쪽 자식이 오른쪽보다 작을 수도, 클 수도 있어요.
이건 이진 탐색 트리와 결정적으로 다른 점이에요.
이진 탐색 트리는 왼쪽이 항상 작고 오른쪽이 크지만, 힙은 그렇지 않아요.
그림 아래쪽 배열 표현을 보세요.
힙은 트리이지만 실제로는 배열 하나로 저장돼요.
레벨 순서대로 왼쪽에서 오른쪽으로 배열에 넣으면 되거든요.
완전 이진 트리라서 빈 공간이 없어요 — 배열에 딱 맞아떨어져요.
최소 힙의 가장 큰 장점은 최솟값을 O(1)에 바로 꺼낼 수 있다는 거예요.
배열의 0번 인덱스가 곧 루트니까요.
삽입과 삭제는 O(log n)이에요 — 트리 높이만큼만 이동하면 돼요.
왜 힙이 필요할까요? 매번 최솟값이나 최댓값이 필요한 상황이 많아요.
예를 들어 응급실에서 가장 급한 환자를 먼저 치료하는 것처럼요.
정렬된 배열로도 되지만 삽입이 O(n)이라 힙이 훨씬 효율적이에요.
이제 힙이 어떻게 배열로 구현되는지 자세히 알아볼게요.