힙: 응급실의 우선순위

프롤로그 - "저 먼저 왔는데요!"

병원 응급실에서 목격한 장면:

환자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) 정렬을 매번 해?"

처음엔 뭐가 이해가 안 갔나

• 힙이 트리라고?
• 왜 부모가 자식보다 커야 해?
• 최댓값이 O(1)인 게 대단한 거야?
• Min Heap vs Max Heap 뭐가 다른 거야?

무엇보다 "Queue랑 뭐가 다른 거야?"

Queue도 데이터 넣고 빼는 건데, 힙도 넣고 빼는 거고. 왜 굳이 트리 구조로 만드는지 와닿지 않았습니다. 게다가 "완전 이진 트리"라는 용어도 생소했고, 배열로 트리를 표현한다는 게 직관적이지 않았습니다.

또 하나 헷갈렸던 건 "Memory Heap"과의 차이입니다. C/C++에서 동적 메모리 할당할 때 "힙 영역"이라고 하는데, 자료구조 힙과 이름만 같을 뿐 완전히 다른 개념입니다. 메모리 힙은 그냥 빈 공간 덩어리이고, 자료구조 힙은 우선순위 관리를 위한 트리 구조입니다. 처음엔 이 둘을 혼동해서 더 헷갈렸습니다.

깨달음의 순간 - "응급실 vs 은행"

시니어의 비유:

일반 Queue (은행): "선착순이야. 먼저 온 사람이 먼저 처리돼."

Priority Queue (응급실): "위급한 사람이 먼저야. 나중에 와도 심장마비 환자가 우선."

Heap: "Priority Queue를 구현하는 가장 효율적인 자료구조야. 맨 위(Root)에 항상 가장 중요한 애가 있어."

"아, 중요도 순서구나!"

은행은 누가 먼저 왔는지(시간)만 보지만, 응급실은 누가 더 위급한지(우선순위)를 봅니다. 힙은 바로 이 "우선순위 관리"를 효율적으로 하는 도구였습니다. 그리고 Root에 항상 최댓값(Max Heap) 또는 최솟값(Min Heap)이 있어서, "가장 중요한 거 하나만 빠르게 찾으면 된다"는 철학이 담겨 있다는 걸 깨달았습니다.

1. Heap의 구조 - 완전 이진 트리

Max Heap (최대 힙)

규칙: 부모 ≥ 자식

      100  ← 최댓값 (Root)
     /   \
   50     80
  / \    / \
 30  40 60  70

특징:

• Root = 최댓값
• 부모 > 자식 (항상)
• 좌우 자식 순서는 상관없음

예를 들어 50과 80의 위치를 바꿔도 됩니다. 중요한 건 100이 Root에 있다는 것뿐입니다.

Min Heap (최소 힙)

규칙: 부모 ≤ 자식

       5  ← 최솟값
      / \
    10  15
   / \
  20  30

Min Heap은 Root에 최솟값이 있습니다. 다익스트라 최단 경로 알고리즘에서 "가장 가까운 노드"를 찾을 때 Min Heap을 씁니다.

완전 이진 트리란?

"Complete Binary Tree" = 왼쪽부터 빈틈없이 채워진 트리

     O
    / \
   O   O
  / \
 O   O  ← 이 순서로 채워짐

나는 이걸 "아파트 입주"에 비유해서 이해했습니다. 아파트 입주할 때 101호부터 순서대로 들어가지, 중간 호수 비워두고 1001호부터 입주하진 않잖아요? 힙도 마찬가지입니다. 배열 인덱스 0부터 순서대로 채워 넣습니다.

2. 배열로 구현

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)이고요. 이렇게 계산만으로 트리 구조를 표현합니다.

3. 삽입 (Insert): O(log n)

과정

1. 맨 끝에 추가
2. 부모와 비교
3. 부모보다 크면 Swap (Bubble Up)
4. 반복

나는 이걸 "신입사원 승진"에 비유했습니다. 신입은 일단 맨 아래(말단)에서 시작합니다. 그런데 성과가 좋으면 위로 올라갑니다. 부모(상사)보다 뛰어나면 자리를 바꿉니다. 계속 올라가다가 더 이상 올라갈 수 없는 위치에 정착합니다.

코드

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을 삽입하면:

1. 맨 끝에 추가: [100, 50, 150]
2. 부모(100)와 비교 → 150 > 100 → Swap
3. 최종: [150, 50, 100]

이 과정이 O(log n)인 이유는 트리의 높이만큼만 올라가면 되기 때문입니다. 완전 이진 트리의 높이는 log n이니까요.

4. 삭제 (Extract Max): O(log n)

과정

1. Root (최댓값) 제거
2. 맨 끝 요소를 Root로 이동
3. 자식과 비교
4. 자식보다 작으면 Swap (Bubble Down)
5. 반복

나는 이걸 "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

5. Heapify: 배열을 힙으로 만들기 O(n)

"이미 있는 배열을 힙으로 바꾸려면?"

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)이 됩니다.

이걸 "건물 정리"에 비유했습니다. 건물 꼭대기부터 정리하는 게 아니라, 아래층부터 정리하면 효율적입니다. 아래층은 이미 정리되어 있으니 위층만 정리하면 되거든요.

6. 실제 - 작업 스케줄러

제가 회사에서 만든 코드:

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을 쓰니 성능이 확 좋아졌습니다.

7. Heap vs 정렬된 배열

정렬된 배열

const tasks = [5, 10, 15];

// 최댓값 찾기: O(1)
const max = tasks[tasks.length - 1];

// 삽입: O(n) - 정렬 유지 필요
tasks.splice(index, 0, 12);  // 올바른 위치 찾기

문제: 삽입이 느림!

예를 들어 [5, 10, 15]에 12를 넣으려면:

1. 12가 들어갈 위치 찾기 (10과 15 사이)
2. 배열 뒷부분 한 칸씩 밀기
3. 12 삽입

이 과정이 O(n)입니다.

Heap

// 최댓값 찾기: O(1)
const max = heap.heap[0];

// 삽입: O(log n)
heap.insert(12);

장점: 삽입/삭제가 빠름!

나는 이걸 "책상 정리"에 비유했습니다. 정렬된 배열은 책을 항상 가나다 순으로 꽂아야 하는 서재입니다. 새 책이 오면 중간에 끼워 넣느라 다른 책들을 다 밀어야 합니다. 반면 힙은 "제일 중요한 책은 책상 위에" 규칙만 지키는 겁니다. 나머지는 대충 쌓아둬도 되니 훨씬 빠릅니다.

8. 실제 - Top K 문제

문제

"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)

• 100만 개 모두 정렬 (낭비)

✅ 좋은 방법 (Min Heap)

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)

• k=10이면 → O(n log 10) ≈ O(n) 🚀 빠름!

"왜 Min Heap?"

처음엔 이게 헷갈렸습니다. 최댓값 찾는데 왜 Min Heap? 하지만 생각해보니:

• 크기 10인 Min Heap을 유지
• 새 숫자가 Heap의 최솟값보다 크면 최솟값을 버리고 새 숫자 삽입
• 결국 가장 큰 10개만 남음

나는 이걸 "대학 입학 커트라인"에 비유했습니다. 정원 10명인 학과에 지원자가 계속 들어옵니다. 현재 10등 학생의 점수가 커트라인입니다. 새 지원자가 커트라인보다 높으면 합격, 10등 학생이 떨어집니다. 최종적으로 상위 10명만 남습니다.

9. 실제 - 다익스트라 알고리즘

최단 경로 알고리즘에서 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?

• 가장 가까운 노드를 O(log n)에 찾음
• 배열이면 O(n) (느림)

다익스트라는 "가장 가까운 노드부터 방문"하는 알고리즘입니다. Min Heap을 쓰면 항상 거리가 가장 짧은 노드를 O(log n)에 찾을 수 있습니다.

10. Python heapq 모듈

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(최댓값)가 됩니다.

11. 두 개의 Heap으로 중앙값 찾기

문제: 스트림에서 계속 숫자가 들어올 때 중앙값을 실시간으로 찾기

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: 작은 쪽 절반 (Root = 작은 쪽 최댓값)
• Min Heap: 큰 쪽 절반 (Root = 큰 쪽 최솟값)
• 두 Heap의 Root가 중앙값 근처

나는 이걸 "시소 균형"에 비유했습니다. 왼쪽(Max Heap)과 오른쪽(Min Heap)의 무게가 비슷하게 유지되도록 숫자를 분배합니다. 중앙값은 두 Heap의 Root 평균입니다.

12. OS 프로세스 스케줄링

"운영체제도 Heap을 쓴다!"

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)에서 가장 위급한(우선순위 높은) 환자부터 치료합니다.

13. Heap Sort 알고리즘 O(n log n)

"Heap으로 정렬도 가능하다!"

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) 정렬이지만, 추가 메모리가 필요 없다는 장점이 있습니다.

14. K-way Merge

문제: 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)

• N = 전체 요소 개수
• k = 배열 개수

k개 배열을 Merge Sort로 합치면 O(Nk)인데, Heap을 쓰면 O(N log k)로 줄어듭니다. 나는 이걸 "여러 줄 서기"에 비유했습니다. k개 줄에서 가장 앞사람(최솟값)을 뽑고, 그 줄의 다음 사람을 넣습니다. 이걸 반복하면 전체 순서가 나옵니다.

15. JavaScript의 내장 Heap?

안타깝게도 없습니다! 😢

// ❌ JavaScript에 없음
const heap = new PriorityQueue();  // Error!

해결책:

1. 직접 구현 (위 코드)
2. 라이브러리: heap-js, priorityqueuejs

npm 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 라이브러리가 많습니다.

16. 정리 - Heap 체크리스트

항목	설명
구조	완전 이진 트리 (배열로 구현)
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을 봅니다:

• OS 프로세스 스케줄링 = Heap
• 병원 응급실 = Priority Queue (Heap)
• Google 검색 결과 = Top K (Heap)
• 다익스트라 최단 경로 = Heap
• 실시간 중앙값 계산 = Two Heaps

"중요한 건 먼저 처리한다."

이 한 문장이 Heap의 본질입니다.

제가 배운 교훈:

"선착순(FIFO)은 공평하지만, 우선순위(Heap)가 효율적이다."

회사에서 작업 스케줄러를 만들면서 배운 가장 큰 깨달음은 "정렬은 과한 낭비"라는 점입니다. 전체를 정렬할 필요 없이, 지금 당장 가장 중요한 것만 빠르게 찾으면 됩니다. 그게 Heap의 철학입니다.

Heap을 공부하면서 "자료구조는 철학이다"라는 생각을 했습니다. 배열, 링크드 리스트, 트리, 힙... 각각의 자료구조는 세상을 바라보는 방식이 다릅니다. 힙은 "우선순위가 전부"라는 세계관을 가진 자료구조입니다.