힙 — 최솟값을 O(1)에 꺼내는 완전 이진 트리
정렬하지 않고도 항상 가장 작은(또는 큰) 값을 빠르게 꺼낼 수 있는 방법이 있을까요?
힙이란
힙(Heap)은 완전 이진 트리 기반의 자료구조로, 부모 노드가 자식 노드보다 항상 작거나(최소 힙) 크거나(최대 힙) 한 성질을 만족합니다.
최소 힙 (Min Heap)
1
/ \
3 5
/ \ /
7 9 11
- 부모 ≤ 자식
- 루트가 항상 최솟값
최대 힙 (Max Heap)
11
/ \
9 5
/ \ /
7 3 1
- 부모 ≥ 자식
- 루트가 항상 최댓값
왜 필요한가
| 방법 | 최솟값 조회 | 삽입 | 삭제(최솟값) |
|---|---|---|---|
| 정렬된 배열 | O(1) | O(n) | O(n) |
| 정렬되지 않은 배열 | O(n) | O(1) | O(n) |
| ** 힙** | O(1) | O(log n) | O(log n) |
"항상 최솟값(또는 최댓값)을 빠르게 꺼내면서, 삽입도 효율적으로 해야 하는" 상황에서 힙이 최적입니다.
배열 기반 구현
완전 이진 트리는 ** 배열로 자연스럽게 표현 **됩니다.
트리: 1
/ \
3 5
/ \ /
7 9 11
배열: [1, 3, 5, 7, 9, 11]
인덱스: 0 1 2 3 4 5
인덱스 관계 (0-indexed)
int parent(int i) { return (i - 1) / 2; }
int leftChild(int i) { return 2 * i + 1; }
int rightChild(int i) { return 2 * i + 2; }
포인터가 필요 없으므로 메모리 효율적이고, 배열의 연속 메모리 접근으로 캐시 효율도 좋습니다.
핵심 연산
Sift Up (상향 이동) — 삽입 시 사용
새 요소를 배열 끝에 추가하고, 부모보다 작으면 위로 올립니다.
private void siftUp(int index) {
while (index > 0) {
int parentIdx = parent(index);
if (heap[index] < heap[parentIdx]) {
swap(index, parentIdx);
index = parentIdx;
} else {
break;
}
}
}
삽입 과정 (값 2를 최소 힙에 삽입):
Step 1: 끝에 추가 Step 2: 부모(9)와 비교 Step 3: 부모(3)와 비교
1 1 1
/ \ / \ / \
3 5 3 5 2 5
/ \ / \ / \ / \ / \ / \
7 9 11 [2] 7 [2] 11 9 7 3 11 9
2 < 9 → 교환 2 < 3 → 교환
Sift Down (하향 이동) — 삭제 시 사용
루트를 제거하고, 마지막 요소를 루트로 올린 뒤 아래로 내립니다.
private void siftDown(int index) {
int size = heap.length;
while (leftChild(index) < size) {
int smallest = index;
int left = leftChild(index);
int right = rightChild(index);
if (left < size && heap[left] < heap[smallest]) {
smallest = left;
}
if (right < size && heap[right] < heap[smallest]) {
smallest = right;
}
if (smallest != index) {
swap(index, smallest);
index = smallest;
} else {
break;
}
}
}
전체 구현
public class MinHeap {
private int[] heap;
private int size;
private int capacity;
public MinHeap(int capacity) {
this.capacity = capacity;
this.heap = new int[capacity];
this.size = 0;
}
// 삽입: O(log n)
public void insert(int value) {
if (size >= capacity) throw new RuntimeException("힙이 가득 참");
heap[size] = value;
siftUp(size);
size++;
}
// 최솟값 조회: O(1)
public int peek() {
if (size == 0) throw new RuntimeException("힙이 비어있음");
return heap[0];
}
// 최솟값 추출: O(log n)
public int poll() {
if (size == 0) throw new RuntimeException("힙이 비어있음");
int min = heap[0];
heap[0] = heap[--size];
siftDown(0);
return min;
}
private void siftUp(int index) {
while (index > 0) {
int parentIdx = (index - 1) / 2;
if (heap[index] < heap[parentIdx]) {
swap(index, parentIdx);
index = parentIdx;
} else break;
}
}
private void siftDown(int index) {
while (2 * index + 1 < size) {
int smallest = index;
int left = 2 * index + 1;
int right = 2 * index + 2;
if (left < size && heap[left] < heap[smallest]) smallest = left;
if (right < size && heap[right] < heap[smallest]) smallest = right;
if (smallest != index) {
swap(index, smallest);
index = smallest;
} else break;
}
}
private void swap(int i, int j) {
int temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
}
Heapify — O(n) 힙 구축
n개의 원소를 하나씩 삽입하면 O(n log n)이지만, 하향식 heapify 를 사용하면 O(n)에 구축할 수 있습니다.
// 배열을 힙으로 변환: O(n)
public static void heapify(int[] arr) {
int n = arr.length;
// 마지막 비-리프 노드부터 거꾸로
for (int i = n / 2 - 1; i >= 0; i--) {
siftDown(arr, n, i);
}
}
O(n)인 이유를 직관적으로 설명하면 다음과 같습니다.
- 리프 노드(약 n/2개)는 아무 작업 불필요 → 0회
- 높이 1의 노드(약 n/4개)는 최대 1번 비교 → n/4회
- 높이 2의 노드(약 n/8개)는 최대 2번 비교 → 2n/8회
- 합산: n/4 + 2n/8 + 3n/16 + ... ≈ O(n)
Java PriorityQueue
Java의 PriorityQueue는 내부적으로 최소 힙입니다.
import java.util.PriorityQueue;
// 최소 힙 (기본)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(5);
minHeap.offer(2);
minHeap.offer(8);
minHeap.offer(1);
minHeap.peek(); // 1
minHeap.poll(); // 1
minHeap.poll(); // 2
// 최대 힙
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.offer(5);
maxHeap.offer(2);
maxHeap.offer(8);
maxHeap.peek(); // 8
// 커스텀 비교: 문자열 길이순
PriorityQueue<String> byLength = new PriorityQueue<>(
Comparator.comparingInt(String::length)
);
PriorityQueue 주의사항
// PriorityQueue는 정렬된 것이 아닙니다!
PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(5, 3, 7, 1));
System.out.println(pq); // [1, 3, 7, 5] — 힙 순서이지, 정렬된 것이 아님
// 정렬된 순서로 꺼내려면 poll()을 반복
while (!pq.isEmpty()) {
System.out.print(pq.poll() + " "); // 1 3 5 7 — 이때 정렬됨
}
힙 정렬 (Heap Sort)
힙을 이용한 정렬 알고리즘입니다.
public static void heapSort(int[] arr) {
int n = arr.length;
// 1. 최대 힙 구축: O(n)
for (int i = n / 2 - 1; i >= 0; i--) {
siftDown(arr, n, i);
}
// 2. 하나씩 추출하여 정렬: O(n log n)
for (int i = n - 1; i > 0; i--) {
swap(arr, 0, i); // 최댓값을 끝으로
siftDown(arr, i, 0); // 나머지를 다시 힙으로
}
}
- 시간 복잡도: O(n log n) (항상)
- 공간 복잡도: O(1) (제자리 정렬)
- 단점: 캐시 효율이 나쁘고, 실제 성능은 QuickSort보다 느린 경우가 많습니다
백엔드 실무 연결
Top-K 문제
대량의 데이터에서 상위 K개를 구할 때 힙이 효율적입니다.
// 100만 개 중 상위 10개 찾기
// 최소 힙을 크기 10으로 유지
public List<Integer> topK(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : nums) {
minHeap.offer(num);
if (minHeap.size() > k) {
minHeap.poll(); // 가장 작은 것 제거
}
}
// 힙에 남은 k개가 상위 k개
return new ArrayList<>(minHeap);
}
로그 시스템에서의 활용
// 최근 에러 로그 중 심각도가 높은 K개 유지
PriorityQueue<LogEntry> criticalLogs = new PriorityQueue<>(
Comparator.comparingInt(LogEntry::getSeverity)
);
정리
- 힙은 ** 완전 이진 트리 **로, 부모가 자식보다 항상 작거나(최소 힙) 큽니다(최대 힙).
- ** 배열로 구현 **하며, 인덱스 계산으로 부모/자식을 찾습니다.
- 삽입은 sift up, 삭제는 sift down 연산을 사용합니다.
- Heapify 로 배열을 O(n)에 힙으로 변환할 수 있습니다.
- Java의
PriorityQueue가 힙의 대표적 구현이며, 기본은 최소 힙 입니다. - Top-K 문제, 스케줄링, 이벤트 처리 등 다양한 실무 상황에서 활용됩니다.
댓글 로딩 중...