도입
BST가 왼쪽과 오른쪽에 정렬 규칙을 넣어 검색 범위를 줄이는 구조라면, 힙은 부모와 자식 사이에만 우선순위 규칙을 넣어 루트에서 항상 가장 중요한 값을 꺼낼 수 있게 만든 구조입니다.
그래서 힙은 전체 데이터가 완전히 정렬되어 있지는 않지만, 현재 시점에 가장 작은 값이나 가장 큰 값을 반복해서 처리해야 하는 문제에서 매우 강합니다. 대표적으로 priority queue와 heapsort가 여기에 해당합니다.
즉 힙을 이해한다는 것은 트리 구조를 하나 더 아는 것이 아니라, 정렬 전체보다 우선순위의 루트 접근을 더 중요하게 보는 자료구조 설계를 이해하는 일에 가깝습니다.
필요성
예를 들어 작업 스케줄링, 이벤트 처리, shortest path 계열 알고리즘, top-k 문제처럼 “지금 가장 우선순위가 높은 원소 하나”를 계속 뽑아야 하는 문제는 생각보다 많습니다.
이런 상황에서 전체 정렬을 매번 다시 하는 것은 비효율적입니다. 힙은 전체 순서를 완벽히 유지하는 대신, 루트가 항상 가장 작은 값 또는 가장 큰 값이 되도록 유지해 필요한 원소를 빠르게 얻도록 설계됩니다.
그래서 힙의 강점은 “전체를 다 정렬한다”보다 “다음 우선순위 하나를 반복해서 뽑는다”는 작업 모델에 있습니다.
- 최솟값 또는 최댓값을 반복적으로 꺼내야 할 때
- priority queue를 효율적으로 구현하고 싶을 때
- 전체 정렬보다 루트 우선 접근이 중요한 경우
- 완전 이진 트리의 배열 표현으로 메모리를 compact하게 쓰고 싶을 때
정의
힙의 정의는 크게 두 가지 조건으로 이루어집니다.
첫째는 shape property입니다. 힙은 보통 complete binary tree여야 합니다. 즉 마지막 레벨을 제외한 모든 레벨이 꽉 차 있고, 마지막 레벨은 왼쪽부터 채워집니다.
둘째는 heap property입니다. min-heap이라면 부모가 자식보다 작거나 같고, max-heap이라면 부모가 자식보다 크거나 같습니다. 이 규칙 덕분에 루트가 항상 가장 작은 값 또는 가장 큰 값을 가집니다.
"힙의 본질은 전체 정렬이 아니라
루트가 항상 가장 중요한 값이 되도록 부모-자식 관계만 강하게 제약하는 데 있습니다."
핵심 원리
BST는 왼쪽 전체가 더 작고 오른쪽 전체가 더 크다는 강한 규칙을 가집니다. 반면 힙은 부모와 자식 사이에만 비교 규칙이 있습니다. 따라서 같은 레벨의 형제 노드끼리는 누가 더 큰지, 더 작은지가 보장되지 않습니다.
이 점 때문에 힙은 정렬 검색 구조라기보다 우선순위 구조에 더 가깝습니다. 대신 complete binary tree라는 shape property를 갖기 때문에 높이가 작고, 배열 기반으로 compact하게 표현하기 쉽습니다.
결국 힙은 “전체 순서를 아는 구조”가 아니라 “루트 하나는 확실히 안다”는 구조입니다. 이 한 가지를 강하게 보장하는 대신, 그 외의 정렬 정보는 최소한만 유지합니다.
그래서 힙은 정렬 자체보다는 next minimum 또는 next maximum을 반복해서 뽑아야 하는 문제와 가장 잘 맞습니다.
Heap Thinking
1) complete binary tree 형태를 유지한다
2) 부모-자식 사이의 우선순위 규칙을 지킨다
3) 루트가 항상 최소값 또는 최대값이 된다
4) 삽입은 아래에 넣고 위로 올린다
5) 루트 제거는 마지막 원소를 올리고 아래로 내린다핵심 불변식
| 불변식 | 의미 | 실무 해석 |
|---|---|---|
| Shape Property | complete binary tree 형태 유지 | 배열 기반 표현이 가능하고 높이가 작게 유지됨 |
| Min-Heap Property | 부모 ≤ 자식 | 루트가 항상 최소값 |
| Max-Heap Property | 부모 ≥ 자식 | 루트가 항상 최대값 |
| Partial Order | 전체 정렬이 아니라 부분 정렬 | 형제나 다른 서브트리끼리 순서는 보장되지 않음 |
기본 구조
일반 이진 트리는 보통 노드 객체와 포인터로 구현하지만, binary heap은 배열로 표현하는 편이 훨씬 자연스럽습니다. complete binary tree는 노드의 위치가 사실상 하나의 shape로 정해지기 때문입니다.
0-based 배열 표현을 쓰면 루트는 인덱스 0에 있고, 왼쪽 자식은 2i+1, 오른쪽 자식은 2i+2, 부모는 (i-1)/2 로 계산할 수 있습니다. 별도 포인터를 저장하지 않아도 된다는 점이 큰 장점입니다.
binary-heap/
├── array
│ ├── root at index 0
│ ├── left(i) = 2i + 1
│ ├── right(i) = 2i + 2
│ └── parent(i) = (i - 1) / 2
└── complete binary tree shape
└── level-order 로 빈칸 없이 저장기본 구현
class MinHeap {
private java.util.ArrayList<Integer> a = new java.util.ArrayList<>();
private int parent(int i) { return (i - 1) / 2; }
private int left(int i) { return 2 * i + 1; }
private int right(int i) { return 2 * i + 2; }
public void push(int x) {
a.add(x);
bubbleUp(a.size() - 1);
}
public int peek() {
return a.get(0);
}
public int pop() {
int root = a.get(0);
int last = a.remove(a.size() - 1);
if (!a.isEmpty()) {
a.set(0, last);
trickleDown(0);
}
return root;
}
private void bubbleUp(int i) {
while (i > 0) {
int p = parent(i);
if (a.get(p) <= a.get(i)) break;
swap(i, p);
i = p;
}
}
private void trickleDown(int i) {
while (true) {
int l = left(i);
int r = right(i);
int smallest = i;
if (l < a.size() && a.get(l) < a.get(smallest)) smallest = l;
if (r < a.size() && a.get(r) < a.get(smallest)) smallest = r;
if (smallest == i) break;
swap(i, smallest);
i = smallest;
}
}
private void swap(int i, int j) {
int tmp = a.get(i);
a.set(i, a.get(j));
a.set(j, tmp);
}
}패턴 1. 최소 힙과 최대 힙
min-heap에서는 가장 작은 값이 루트에 있고, max-heap에서는 가장 큰 값이 루트에 있습니다. 비교 연산 방향만 바꾸면 구현은 거의 대칭적입니다.
차이는 사용 목적에서 드러납니다. 작업 스케줄링에서 가장 이른 마감 시간을 먼저 꺼내고 싶다면 min-heap이 자연스럽고, 우선순위가 가장 큰 작업을 먼저 처리하려면 max-heap이 더 잘 맞습니다.
Min-Heap
- 부모 ≤ 자식
- root = 최소값
Max-Heap
- 부모 ≥ 자식
- root = 최대값패턴 2. 우선순위 큐와 BST 차이
| 관점 | 힙(Heap) | BST |
|---|---|---|
| 핵심 목표 | 루트에서 최소/최대값 빠르게 꺼내기 | 정렬 기반 검색과 순서 질의 |
| 정렬 정보 | 부모-자식 사이만 부분 정렬 | 왼쪽 전체/오른쪽 전체에 대한 강한 정렬 규칙 |
| 루트 의미 | 항상 최소값 또는 최대값 | 중앙 분기 기준점 |
| 중위 순회 | 정렬 순이 아님 | 정렬 순이 됨 |
| 대표 용도 | priority queue, heapsort | ordered set/map, predecessor/successor 검색 |
즉 힙은 “가장 작은 것 하나” 또는 “가장 큰 것 하나”를 빠르게 꺼내는 구조이고, BST는 “정렬 질의를 풍부하게 처리하는 구조”라고 보면 차이가 분명해집니다.
패턴 3. heapify 와 heapsort
힙을 만드는 방법은 두 가지로 생각할 수 있습니다. 하나는 빈 힙에 원소를 하나씩 넣는 방식이고, 다른 하나는 이미 있는 배열을 한 번에 heap으로 바꾸는 heapify 방식입니다.
또 힙은 정렬 알고리즘과도 직접 연결됩니다. NIST가 설명하듯 heapsort는 힙을 만든 다음 최대값을 반복해서 추출하는 방식으로 동작합니다. 즉 힙은 우선순위 큐 구조이면서 동시에 정렬의 기반이기도 합니다.
Heap Workflow
1) 배열을 heapify 하거나
2) 하나씩 push 해서 힙을 만든다
3) root를 반복적으로 pop 하면
4) 우선순위 처리 또는 정렬 과정으로 연결된다한계와 주의점
힙의 가장 큰 장점은 루트 하나를 빠르게 얻는 것이지만, 그만큼 다른 순서 정보는 많이 버립니다. 그래서 힙 안에서 임의 값을 효율적으로 찾거나, predecessor/successor 같은 ordered query를 처리하는 데는 적합하지 않습니다.
또 complete binary tree 모양을 유지해야 하므로, 포인터 기반 일반 트리처럼 자유롭게 가지를 붙이는 구조와는 사용감이 다릅니다. 힙은 우선순위 문제에 매우 좋지만, 모든 트리 문제의 일반 해법은 아닙니다.
마지막으로 힙이 정렬 구조처럼 보여도 실제로는 partial order만 유지한다는 점을 잊기 쉽습니다. 이 오해 때문에 힙 내부를 순서대로 훑으면 정렬되어 있을 것이라고 기대하는 실수가 자주 생깁니다.
- 힙은 전체 정렬 구조가 아니라 partial order 구조임
- 루트는 보장되지만 형제 노드 사이 순서는 보장되지 않음
- 임의 값 탐색이나 ordered query에는 BST보다 부자연스러움
- shape property 와 heap property 둘 다 동시에 유지해야 함
자주 하는 실수
- 힙 내부를 왼쪽부터 보면 정렬되어 있을 것이라고 생각함
- BST와 힙을 둘 다 “검색 트리” 정도로 뭉뚱그려 생각함
- 삽입에서 bubble-up 을 빼먹어 heap invariant 를 깨뜨림
- 루트 제거 후 trickle-down 을 하지 않아 구조를 망가뜨림
- complete binary tree shape 를 유지하지 않고 임의 위치에 노드를 붙임
- min-heap 과 max-heap 비교 방향을 뒤섞음
실무 루틴
- 먼저 필요한 것이 전체 정렬 인지, 최소/최대 반복 추출 인지 구분한다.
- 루트가 최소여야 하는지 최대여야 하는지 보고 min-heap 또는 max-heap 을 정한다.
- complete binary tree 라면 포인터보다 배열 표현 을 먼저 고려한다.
- 삽입은 bubble-up, 제거는 trickle-down 으로 생각하면 구현이 단순해진다.
- 기존 배열이 있다면 하나씩 넣기보다 heapify 경로도 검토한다.
- 정렬 질의가 많다면 heap 대신 BST 또는 balanced BST 가 더 맞는지 다시 본다.
디버깅
parent(i), left(i), right(i) 계산이 맞는지 먼저 본다.peek() 결과가 바로 깨졌는지부터 본다.점검 체크리스트
- min-heap / max-heap 방향이 맞는가
- complete binary tree shape 가 유지되는가
- parent / left / right index 계산이 맞는가
- bubble-up / trickle-down 이 빠지지 않았는가
- root 가 항상 최소값 또는 최대값인가요약
- ✅ 힙은 complete binary tree 와 heap property 를 함께 갖는 구조다.
- ✅ min-heap 은 부모 ≤ 자식, max-heap 은 부모 ≥ 자식이다.
- ✅ 루트는 항상 최소값 또는 최대값을 가진다.
- ✅ binary heap 은 배열로 compact 하게 구현하는 편이 자연스럽다.
- ✅ 0-based 배열에서 왼쪽 자식은
2i+1, 오른쪽 자식은2i+2, 부모는(i-1)/2다. - ✅ 삽입은 bubble-up, 루트 제거는 trickle-down 으로 heap invariant 를 복구한다.
- ✅ 힙은 전체 정렬 구조가 아니라 priority queue 에 최적화된 partial order 구조다.
- ✅ heapify 와 heapsort 까지 연결해서 보면 힙의 실무적 의미가 더 분명해진다.