
힙: 응급실의 우선순위
줄 선 순서대로 치료하는 건 동네 병원(Queue)이고, 응급실은 위급한 사람부터 치료한다(Priority Queue). O(1)의 비밀.

줄 선 순서대로 치료하는 건 동네 병원(Queue)이고, 응급실은 위급한 사람부터 치료한다(Priority Queue). O(1)의 비밀.
내 서버는 왜 걸핏하면 뻗을까? OS가 한정된 메모리를 쪼개 쓰는 처절한 사투. 단편화(Fragmentation)와의 전쟁.

미로를 탈출하는 두 가지 방법. 넓게 퍼져나갈 것인가(BFS), 한 우물만 팔 것인가(DFS). 최단 경로는 누가 찾을까?

이름부터 빠릅니다. 피벗(Pivot)을 기준으로 나누고 또 나누는 분할 정복 알고리즘. 왜 최악엔 느린데도 가장 많이 쓰일까요?

매번 3-Way Handshake 하느라 지쳤나요? 한 번 맺은 인연(TCP 연결)을 소중히 유지하는 법. HTTP 최적화의 기본.

병원 응급실에서 목격한 장면:
환자A (감기, 9시 도착): "저 먼저 왔는데 왜 안 봐주세요?" 간호사: "저분은 심장 환자라서 먼저 봐야 해요." 환자B (심장마비, 10시 도착): (stretcher로 바로 이동)
저: "선착순이 아니네?"
은행 번호표는 FIFO(First In First Out)인데, 응급실은 다릅니다. 심장마비 환자가 감기 환자보다 나중에 와도 먼저 치료받습니다. 나는 이 장면을 보고 "아, 세상엔 선착순이 아닌 시스템도 있구나" 라고 이해했습니다.
회사에서 "작업 스케줄러" 만들라는 업무를 받았습니다.
요구사항:
저: "배열에 넣고 정렬하면 돼죠?"
시니어: "매번 정렬? O(n log n)? 느려. 힙(Heap) 써."
그때부터 힙을 공부했습니다.코드를 작성하다 보니 작업 우선순위 관리가 핵심이었습니다. 사용자가 버튼을 클릭할 때마다 새 작업이 들어오는데, 긴급 작업(서버 다운, 결제 오류)은 일반 작업(로그 정리, 통계 생성)보다 먼저 실행되어야 합니다. 처음엔 배열에 작업을 넣고 매번 sort()를 호출했습니다. 그런데 작업이 1000개, 10000개로 늘어나자 느려지기 시작했습니다.
시니어 개발자가 코드 리뷰에서 한마디 던졌습니다: "힙 쓰면 O(log n)인데 왜 O(n log n) 정렬을 매번 해?"
무엇보다 "Queue랑 뭐가 다른 거야?"
Queue도 데이터 넣고 빼는 건데, 힙도 넣고 빼는 거고. 왜 굳이 트리 구조로 만드는지 와닿지 않았습니다. 게다가 "완전 이진 트리"라는 용어도 생소했고, 배열로 트리를 표현한다는 게 직관적이지 않았습니다.
또 하나 헷갈렸던 건 "Memory Heap"과의 차이입니다. C/C++에서 동적 메모리 할당할 때 "힙 영역"이라고 하는데, 자료구조 힙과 이름만 같을 뿐 완전히 다른 개념입니다. 메모리 힙은 그냥 빈 공간 덩어리이고, 자료구조 힙은 우선순위 관리를 위한 트리 구조입니다. 처음엔 이 둘을 혼동해서 더 헷갈렸습니다.
시니어의 비유:
"아, 중요도 순서구나!"일반 Queue (은행): "선착순이야. 먼저 온 사람이 먼저 처리돼."
Priority Queue (응급실): "위급한 사람이 먼저야. 나중에 와도 심장마비 환자가 우선."
Heap: "Priority Queue를 구현하는 가장 효율적인 자료구조야. 맨 위(Root)에 항상 가장 중요한 애가 있어."
은행은 누가 먼저 왔는지(시간)만 보지만, 응급실은 누가 더 위급한지(우선순위)를 봅니다. 힙은 바로 이 "우선순위 관리"를 효율적으로 하는 도구였습니다. 그리고 Root에 항상 최댓값(Max Heap) 또는 최솟값(Min Heap)이 있어서, "가장 중요한 거 하나만 빠르게 찾으면 된다"는 철학이 담겨 있다는 걸 깨달았습니다.
규칙: 부모 ≥ 자식
100 ← 최댓값 (Root)
/ \
50 80
/ \ / \
30 40 60 70
특징:
예를 들어 50과 80의 위치를 바꿔도 됩니다. 중요한 건 100이 Root에 있다는 것뿐입니다.
규칙: 부모 ≤ 자식
5 ← 최솟값
/ \
10 15
/ \
20 30
Min Heap은 Root에 최솟값이 있습니다. 다익스트라 최단 경로 알고리즘에서 "가장 가까운 노드"를 찾을 때 Min Heap을 씁니다.
"Complete Binary Tree" = 왼쪽부터 빈틈없이 채워진 트리
O
/ \
O O
/ \
O O ← 이 순서로 채워짐
나는 이걸 "아파트 입주"에 비유해서 이해했습니다. 아파트 입주할 때 101호부터 순서대로 들어가지, 중간 호수 비워두고 1001호부터 입주하진 않잖아요? 힙도 마찬가지입니다. 배열 인덱스 0부터 순서대로 채워 넣습니다.
Heap은 완전 이진 트리 → 배열로 표현 가능!
// Max Heap
const heap = [100, 50, 80, 30, 40, 60, 70];
// 인덱스 관계
// parent(i) = Math.floor((i-1)/2)
// left(i) = 2*i + 1
// right(i) = 2*i + 2
인덱스: 0 1 2 3 4 5 6
값: 100 50 80 30 40 60 70
트리 형태:
100 (0)
/ \
50(1) 80(2)
/ \ / \
30(3) 40(4) 60(5) 70(6)
나는 이 부분이 처음엔 신기했습니다. "트리인데 배열로 표현한다고?" 하지만 완전 이진 트리는 빈틈이 없어서 배열 인덱스와 1:1 대응이 됩니다. 부모-자식 관계를 수식으로 표현할 수 있으니 포인터 없이도 트리를 만들 수 있습니다.
예를 들어 인덱스 2 (값 80)의 왼쪽 자식은 2*2+1 = 5 (값 60), 오른쪽 자식은 2*2+2 = 6 (값 70)입니다. 부모는 (2-1)/2 = 0 (값 100)이고요. 이렇게 계산만으로 트리 구조를 표현합니다.
나는 이걸 "신입사원 승진"에 비유했습니다. 신입은 일단 맨 아래(말단)에서 시작합니다. 그런데 성과가 좋으면 위로 올라갑니다. 부모(상사)보다 뛰어나면 자리를 바꿉니다. 계속 올라가다가 더 이상 올라갈 수 없는 위치에 정착합니다.
class MaxHeap {
constructor() {
this.heap = [];
}
insert(value) {
this.heap.push(value);
this.bubbleUp(this.heap.length - 1);
}
bubbleUp(index) {
while (index > 0) {
const parentIndex = Math.floor((index - 1) / 2);
// 부모보다 크면 Swap
if (this.heap[index] > this.heap[parentIndex]) {
[this.heap[index], this.heap[parentIndex]] =
[this.heap[parentIndex], this.heap[index]];
index = parentIndex;
} else {
break;
}
}
}
}
const heap = new MaxHeap();
heap.insert(100);
heap.insert(50);
heap.insert(150); // 150이 Root로 올라감!
console.log(heap.heap); // [150, 50, 100]
150을 삽입하면:
[100, 50, 150][150, 50, 100]이 과정이 O(log n)인 이유는 트리의 높이만큼만 올라가면 되기 때문입니다. 완전 이진 트리의 높이는 log n이니까요.
나는 이걸 "CEO 사퇴 후 승진"에 비유했습니다. CEO(Root)가 사퇴하면, 일단 막내(맨 끝 요소)를 CEO 자리에 앉힙니다. 당연히 능력 부족이니, 부하직원(자식) 중 더 뛰어난 사람과 자리를 바꿉니다. 계속 내려가다가 적절한 위치에 정착합니다.
class MaxHeap {
extractMax() {
if (this.heap.length === 0) return null;
if (this.heap.length === 1) return this.heap.pop();
const max = this.heap[0];
this.heap[0] = this.heap.pop(); // 마지막을 Root로
this.bubbleDown(0);
return max;
}
bubbleDown(index) {
while (true) {
const leftIndex = 2 * index + 1;
const rightIndex = 2 * index + 2;
let largest = index;
// 왼쪽 자식과 비교
if (leftIndex < this.heap.length &&
this.heap[leftIndex] > this.heap[largest]) {
largest = leftIndex;
}
// 오른쪽 자식과 비교
if (rightIndex < this.heap.length &&
this.heap[rightIndex] > this.heap[largest]) {
largest = rightIndex;
}
// Swap 필요 없으면 종료
if (largest === index) break;
[this.heap[index], this.heap[largest]] =
[this.heap[largest], this.heap[index]];
index = largest;
}
}
}
const max = heap.extractMax();
console.log(max); // 150
class MaxHeap {
heapify(arr) {
this.heap = arr;
// 마지막 부모 노드부터 거꾸로 bubbleDown
const lastParent = Math.floor((this.heap.length - 2) / 2);
for (let i = lastParent; i >= 0; i--) {
this.bubbleDown(i);
}
}
}
const heap = new MaxHeap();
heap.heapify([30, 50, 20, 100, 10]);
console.log(heap.heap); // [100, 50, 20, 30, 10]
나는 처음엔 "하나씩 insert하면 O(n log n)인데, heapify는 O(n)이라고?"라고 의심했습니다. 하지만 증명을 보니 leaf 노드(절반)는 이미 힙 조건을 만족하니 작업이 필요 없고, 상위 레벨로 갈수록 노드 수가 적어서 총 작업량이 O(n)이 됩니다.
이걸 "건물 정리"에 비유했습니다. 건물 꼭대기부터 정리하는 게 아니라, 아래층부터 정리하면 효율적입니다. 아래층은 이미 정리되어 있으니 위층만 정리하면 되거든요.
제가 회사에서 만든 코드:
class TaskScheduler {
constructor() {
this.heap = new MaxHeap();
}
addTask(task) {
this.heap.insert(task);
}
executeNext() {
const task = this.heap.extractMax();
console.log(`Executing: ${task.name} (Priority: ${task.priority})`);
return task;
}
}
const scheduler = new TaskScheduler();
// 작업 추가 (우선순위 부여)
scheduler.addTask({ name: 'Bug Fix', priority: 10 });
scheduler.addTask({ name: 'Feature', priority: 5 });
scheduler.addTask({ name: 'Critical Bug', priority: 15 });
// 높은 우선순위부터 실행
scheduler.executeNext(); // Critical Bug (15)
scheduler.executeNext(); // Bug Fix (10)
scheduler.executeNext(); // Feature (5)
결국 이거였다: 작업 스케줄러는 Priority Queue고, Priority Queue의 핵심은 Heap입니다. 매번 정렬하는 대신 Heap을 쓰니 성능이 확 좋아졌습니다.
const tasks = [5, 10, 15];
// 최댓값 찾기: O(1)
const max = tasks[tasks.length - 1];
// 삽입: O(n) - 정렬 유지 필요
tasks.splice(index, 0, 12); // 올바른 위치 찾기
문제: 삽입이 느림!
예를 들어 [5, 10, 15]에 12를 넣으려면:
이 과정이 O(n)입니다.
// 최댓값 찾기: O(1)
const max = heap.heap[0];
// 삽입: O(log n)
heap.insert(12);
장점: 삽입/삭제가 빠름!
나는 이걸 "책상 정리"에 비유했습니다. 정렬된 배열은 책을 항상 가나다 순으로 꽂아야 하는 서재입니다. 새 책이 오면 중간에 끼워 넣느라 다른 책들을 다 밀어야 합니다. 반면 힙은 "제일 중요한 책은 책상 위에" 규칙만 지키는 겁니다. 나머지는 대충 쌓아둬도 되니 훨씬 빠릅니다.
"100만 개 숫자 중 가장 큰 10개 찾기"
const arr = [/* 100만 개 */];
arr.sort((a, b) => b - a); // O(n log n) 😱
const top10 = arr.slice(0, 10);
시간 복잡도: O(n log n)
class MinHeap {
// (구현 생략)
}
function topK(arr, k) {
const heap = new MinHeap();
arr.forEach(num => {
heap.insert(num);
// 크기 유지
if (heap.size() > k) {
heap.extractMin();
}
});
return heap.heap;
}
const top10 = topK(arr, 10);
시간 복잡도: O(n log k)
처음엔 이게 헷갈렸습니다. 최댓값 찾는데 왜 Min Heap? 하지만 생각해보니:
나는 이걸 "대학 입학 커트라인"에 비유했습니다. 정원 10명인 학과에 지원자가 계속 들어옵니다. 현재 10등 학생의 점수가 커트라인입니다. 새 지원자가 커트라인보다 높으면 합격, 10등 학생이 떨어집니다. 최종적으로 상위 10명만 남습니다.
최단 경로 알고리즘에서 Heap 사용:
function dijkstra(graph, start) {
const distances = { [start]: 0 };
const heap = new MinHeap();
heap.insert({ node: start, dist: 0 });
while (heap.size() > 0) {
const { node, dist } = heap.extractMin();
graph[node].forEach(({ to, weight }) => {
const newDist = dist + weight;
if (!distances[to] || newDist < distances[to]) {
distances[to] = newDist;
heap.insert({ node: to, dist: newDist });
}
});
}
return distances;
}
왜 Heap?
다익스트라는 "가장 가까운 노드부터 방문"하는 알고리즘입니다. Min Heap을 쓰면 항상 거리가 가장 짧은 노드를 O(log n)에 찾을 수 있습니다.
Python은 내장 heapq 모듈이 있습니다:
import heapq
# Min Heap (기본)
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 5)
print(heapq.heappop(heap)) # 1 (최솟값)
# Max Heap (음수 트릭)
max_heap = []
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -5)
print(-heapq.heappop(max_heap)) # 5 (최댓값)
Python의 heapq는 Min Heap만 지원합니다. Max Heap을 쓰려면 "음수로 바꿔서 넣기" 트릭을 씁니다. -3, -1, -5를 넣으면 -5가 최솟값이고, 꺼낼 때 다시 음수를 곱하면 5(최댓값)가 됩니다.
문제: 스트림에서 계속 숫자가 들어올 때 중앙값을 실시간으로 찾기
class MedianFinder {
constructor() {
this.maxHeap = new MaxHeap(); // 작은 쪽 절반
this.minHeap = new MinHeap(); // 큰 쪽 절반
}
addNum(num) {
// 일단 maxHeap에 추가
this.maxHeap.insert(num);
// maxHeap의 최댓값을 minHeap으로 이동
this.minHeap.insert(this.maxHeap.extractMax());
// 크기 균형 맞추기
if (this.maxHeap.size() < this.minHeap.size()) {
this.maxHeap.insert(this.minHeap.extractMin());
}
}
findMedian() {
if (this.maxHeap.size() > this.minHeap.size()) {
return this.maxHeap.heap[0];
} else {
return (this.maxHeap.heap[0] + this.minHeap.heap[0]) / 2;
}
}
}
const mf = new MedianFinder();
mf.addNum(1);
mf.addNum(2);
console.log(mf.findMedian()); // 1.5
mf.addNum(3);
console.log(mf.findMedian()); // 2
아이디어:
나는 이걸 "시소 균형"에 비유했습니다. 왼쪽(Max Heap)과 오른쪽(Min Heap)의 무게가 비슷하게 유지되도록 숫자를 분배합니다. 중앙값은 두 Heap의 Root 평균입니다.
struct Process {
int pid;
int priority;
};
// CPU 스케줄러의 Ready Queue = Priority Queue (Heap)
MaxHeap readyQueue;
void schedule() {
while (true) {
Process p = readyQueue.extractMax(); // 우선순위 높은 프로세스
execute(p);
}
}
운영체제의 프로세스 스케줄러는 Ready Queue에서 우선순위가 가장 높은 프로세스를 선택해 CPU에 할당합니다. 이 Ready Queue가 바로 Heap으로 구현된 Priority Queue입니다.
나는 "응급실의 대기실"과 똑같다고 이해했습니다. 응급실(CPU)은 하나인데 환자(프로세스)는 여러 명입니다. 대기실(Ready Queue)에서 가장 위급한(우선순위 높은) 환자부터 치료합니다.
function heapSort(arr) {
const heap = new MaxHeap();
// 1. 모든 요소를 Heap에 삽입 - O(n log n)
arr.forEach(num => heap.insert(num));
// 2. 하나씩 꺼내면서 배열 채우기 - O(n log n)
const sorted = [];
while (heap.size() > 0) {
sorted.unshift(heap.extractMax()); // 앞에 추가 (내림차순 방지)
}
return sorted;
}
console.log(heapSort([3, 1, 4, 1, 5, 9])); // [1, 1, 3, 4, 5, 9]
더 효율적인 방법 (In-place Heap Sort):
function heapSort(arr) {
const heap = new MaxHeap();
heap.heapify(arr); // O(n)
for (let i = arr.length - 1; i > 0; i--) {
// Root(최댓값)를 맨 뒤로 이동
[heap.heap[0], heap.heap[i]] = [heap.heap[i], heap.heap[0]];
// Heap 크기 줄이고 bubbleDown
heap.heap.length--;
heap.bubbleDown(0);
}
return arr;
}
시간 복잡도: O(n log n) 공간 복잡도: O(1) (In-place)
Heap Sort는 Merge Sort, Quick Sort와 같은 O(n log n) 정렬이지만, 추가 메모리가 필요 없다는 장점이 있습니다.
문제: k개의 정렬된 배열을 하나로 합치기
function mergeKSortedArrays(arrays) {
const heap = new MinHeap();
const result = [];
// 각 배열의 첫 요소를 Heap에 삽입
arrays.forEach((arr, arrayIndex) => {
if (arr.length > 0) {
heap.insert({
value: arr[0],
arrayIndex: arrayIndex,
elementIndex: 0
});
}
});
while (heap.size() > 0) {
const { value, arrayIndex, elementIndex } = heap.extractMin();
result.push(value);
// 다음 요소가 있으면 Heap에 삽입
const nextIndex = elementIndex + 1;
if (nextIndex < arrays[arrayIndex].length) {
heap.insert({
value: arrays[arrayIndex][nextIndex],
arrayIndex: arrayIndex,
elementIndex: nextIndex
});
}
}
return result;
}
const arrays = [
[1, 4, 7],
[2, 5, 8],
[3, 6, 9]
];
console.log(mergeKSortedArrays(arrays)); // [1, 2, 3, 4, 5, 6, 7, 8, 9]
시간 복잡도: O(N log k)
k개 배열을 Merge Sort로 합치면 O(Nk)인데, Heap을 쓰면 O(N log k)로 줄어듭니다. 나는 이걸 "여러 줄 서기"에 비유했습니다. k개 줄에서 가장 앞사람(최솟값)을 뽑고, 그 줄의 다음 사람을 넣습니다. 이걸 반복하면 전체 순서가 나옵니다.
안타깝게도 없습니다! 😢
// ❌ JavaScript에 없음
const heap = new PriorityQueue(); // Error!
해결책:
heap-js, priorityqueuejsnpm install heap-js
const { Heap } = require('heap-js');
const maxHeap = new Heap((a, b) => b - a);
maxHeap.push(10);
maxHeap.push(5);
maxHeap.push(15);
console.log(maxHeap.pop()); // 15
나는 처음 JavaScript로 힙을 구현하려다가 "왜 내장 Heap이 없지?"라고 의아했습니다. Python은 heapq가 있는데 말이죠. 알고보니 JavaScript는 Priority Queue 수요가 상대적으로 적어서 내장하지 않았다고 합니다. 대신 npm 라이브러리가 많습니다.
| 항목 | 설명 |
|---|---|
| 구조 | 완전 이진 트리 (배열로 구현) |
| Max Heap | 부모 ≥ 자식 (Root = 최댓값) |
| Min Heap | 부모 ≤ 자식 (Root = 최솟값) |
| 삽입 | O(log n) - Bubble Up |
| 삭제 | O(log n) - Bubble Down |
| 최댓값 찾기 | O(1) - Root 확인 |
| Heapify | O(n) - 배열을 힙으로 변환 |
| 용도 | 우선순위 큐, Top K, 다익스트라, OS 스케줄링 |
처음엔 "Queue면 되는데 왜 Heap?"이라고 생각했습니다.
지금은 어디서든 Heap을 봅니다:
이 한 문장이 Heap의 본질입니다.
제가 배운 교훈:
"선착순(FIFO)은 공평하지만, 우선순위(Heap)가 효율적이다."
회사에서 작업 스케줄러를 만들면서 배운 가장 큰 깨달음은 "정렬은 과한 낭비"라는 점입니다. 전체를 정렬할 필요 없이, 지금 당장 가장 중요한 것만 빠르게 찾으면 됩니다. 그게 Heap의 철학입니다.
Heap을 공부하면서 "자료구조는 철학이다"라는 생각을 했습니다. 배열, 링크드 리스트, 트리, 힙... 각각의 자료구조는 세상을 바라보는 방식이 다릅니다. 힙은 "우선순위가 전부"라는 세계관을 가진 자료구조입니다.