Heap

그냥 받아들이기로 했다.

JavaScript에는 내장 힙이 없다.

그래서 지금까지 우선순위 큐 문제를 안 풀었다.

근데 문제는 우선순위 큐 문제가 자주 나온다는 것이다.

결국 우선순위 큐 문제를 풀려면 힙을 직접 구현하는 수밖에 없다.

1. 최소 힙의 원리

힙이란

힙은 최댓값 또는 최솟값을 빠르게 찾고 제거하기 위해 설계된 완전 이진 트리 기반의 자료구조이다.

• 모든 부모는 자신의 자식보다 작거나 같다. (최소 힙 기준)
• 그 규칙의 결과로 루트가 항상 전체 최솟값이 된다.

      1
    /   \
   2     3
  / \
 7   5

"부모 ≤ 자식"은 모든 노드에서 성립하고, 루트는 최솟값이다.

트리인데 왜 배열로 구현하나

완전 이진 트리(complete binary tree)는 위에서 아래로, 왼쪽에서 오른쪽으로 빈틈없이 채워진 트리다.
빈 자리가 없으니, 노드에 순서대로 번호를 매기면 배열 인덱스와 정확히 일치한다.

        [0]
       /   \
     [1]   [2]
     / \   / \
   [3][4][5] [6]

배열: [ 0, 1, 2, 3, 4, 5, 6 ]

인덱스 i에 대해:

부모      = Math.floor((i - 1) / 2)
왼쪽 자식 = i * 2 + 1
오른쪽 자식 = i * 2 + 2

규칙이 깨지면 어떻게 고치나

힙의 연산은 결국 규칙을 잠깐 깨뜨린 뒤, 원소 하나를 제자리로 옮겨 복구한다가 전부다.
복구 방향이 두 가지라서 연산도 두 가지다.

• 삽입: 배열 맨 뒤에 넣는다 → 부모보다 작을 수 있다 → 위로 올린다 (bubble-up)
• 삭제: 루트를 빼고 맨 뒤 원소를 루트에 놓는다 → 자식보다 클 수 있다 → 아래로 내린다 (bubble-down)

둘 다 트리의 높이만큼만 움직인다. 완전 이진 트리의 높이는 log n이니 O(log n).

---

2. 구현: 숫자를 담는 최소 힙

먼저 원시값(숫자)만 다루는 가장 기본형이다.

class MinHeap {
  constructor() {
    this.heap = [];
  }

  size() {
    return this.heap.length;
  }

  peek() {
    return this.heap[0]; // 꺼내지 않고 최솟값만 확인
  }

  push(value) {
    const heap = this.heap;
    heap.push(value);

    // 방금 넣은 마지막 원소의 인덱스에서 출발
    let idx = heap.length - 1;

    // 루트까지 올라간다
    while (idx > 0) {
      const parent = Math.floor((idx - 1) / 2);

      // 부모가 더 작거나 같다 → 규칙 만족 → 끝
      if (heap[parent] <= heap[idx]) break;

      // 아니라면 부모와 교환하고
      [heap[parent], heap[idx]] = [heap[idx], heap[parent]];

      // 부모 자리에서 다시 검사
      idx = parent;
    }
  }

  pop() {
    const heap = this.heap;

    if (heap.length === 0) return undefined;
    if (heap.length === 1) return heap.pop();

    // 반환할 값을 미리 저장
    const min = heap[0];

    // 맨 뒤 원소를 루트로 올린다
    heap[0] = heap.pop(); // 여기서의 pop()은 JS 배열 메서드

    let idx = 0;

    while (true) {
      // 일단 현재 노드가 가장 작다고 가정
      let smallest = idx;
      const left = idx * 2 + 1;
      const right = idx * 2 + 2;

      // 자식이 존재할 때만 비교
      if (left < heap.length && heap[left] < heap[smallest]) smallest = left;
      if (right < heap.length && heap[right] < heap[smallest]) smallest = right;

      // 현재 노드가 제일 작으면 제자리를 찾은 것
      if (smallest === idx) break;

      // 아니라면 바꿔주고
      [heap[idx], heap[smallest]] = [heap[smallest], heap[idx]];

      // 내려간 자리에서 다시 반복
      idx = smallest;
    }

    return min;
  }
}

push 뜯어보기

새 값이 들어갈 자리를 미리 찾지 않는다. 일단 맨 뒤에 던져놓고 위로 올라간다.

[1, 5, 3] 에 2를 넣는다

      1                 (1) 맨 뒤에 추가 → [1, 5, 3, 2], idx=3
    /   \
   5     3
  /
 2                      (2) parent = (3-1)/2 = 1 → heap[1]=5 > 2 → 교환

      1                 → [1, 2, 3, 5], idx=1
    /   \
   2     3
  /
 5                      (3) parent = (1-1)/2 = 0 → heap[0]=1 <= 2 → break

pop 뜯어보기

최솟값은 루트다. 그런데 heap[0]을 그냥 지우면 완전 이진 트리가 깨진다.

그래서 맨 뒤 원소를 루트로 끌어올린 뒤 아래로 내려보낸다.

[1, 2, 3, 5] 에서 pop()

      1                 (1) min = 1 저장
    /   \               (2) 맨 뒤 5를 루트로 → [5, 2, 3]
   2     3
  /
 5

      5                 (3) idx=0: 자식은 2, 3 → 더 작은 쪽은 2 → 교환
    /   \
   2     3

      2                 → [2, 5, 3], idx=1
    /   \               (4) idx=1: 자식 인덱스 3, 4는 범위 밖 → break
   5     3              (5) min = 1 반환

최대 힙이 필요하면

힙을 새로 짤 필요 없다. 비교하는 부등호 방향만 뒤집으면 된다. 비교가 등장하는 곳은 딱 세 군데다.

// push:  <=  →  >=
if (heap[parent] >= heap[idx]) break;

// pop:   <  →  >   (변수명도 smallest → largest)
if (left < heap.length && heap[left] > heap[largest]) largest = left;
if (right < heap.length && heap[right] > heap[largest]) largest = right;

3. 확장: 비교 함수를 받는 힙

위 구현의 한계는 명확하다. 비교가 <, <=로 하드코딩되어 있다.
그래서 담을 수 있는 게 숫자뿐이다.

그런데 실제 문제에서 힙에 배열이나 객체를 넣을 수도 있다.

따라서 "두 원소 중 뭐가 우선인지"를 판단하는 책임을 밖으로 빼야 한다.

비교 함수의 규약

Array.prototype.sort와 같은 규약을 쓰면 외울 게 하나 줄어든다.

compare(a, b) < 0; // a가 b보다 앞선다 (a가 먼저 나와야 한다)
compare(a, b) === 0; // 우선순위가 같다
compare(a, b) > 0; // b가 a보다 앞선다

이 규약 위에서 힙의 규칙은 이렇게 다시 쓰인다.

모든 부모 p와 자식 c에 대해 compare(p, c) <= 0

즉 부모가 자식보다 앞선다.

구현

기존 코드에서 비교하는 세 군데만 바꾸면 된다.

비교 함수는 힙 밖에서 정의하고 생성자로 넘긴다.

힙은 "무엇을 담는지" 몰라도 되고, 문제마다 바뀌는 건 이 함수 하나뿐이다.

const byAsc = (a, b) => a - b; // 오름차순 = 최소 힙
const byDesc = (a, b) => b - a; // 내림차순 = 최대 힙

class Heap {
  constructor(compare) {
    this.heap = [];
    this.compare = compare;
  }

  size() {
    return this.heap.length;
  }

  peek() {
    return this.heap[0];
  }

  push(value) {
    const heap = this.heap;
    heap.push(value);

    let idx = heap.length - 1;

    while (idx > 0) {
      const parent = Math.floor((idx - 1) / 2);

      // heap[parent] <= heap[idx] 를 비교 함수로 표현
      if (this.compare(heap[parent], heap[idx]) <= 0) break;

      [heap[parent], heap[idx]] = [heap[idx], heap[parent]];
      idx = parent;
    }
  }

  pop() {
    const heap = this.heap;

    if (heap.length === 0) return undefined;
    if (heap.length === 1) return heap.pop();

    const top = heap[0]; // 가장 높은 우선순위
    heap[0] = heap.pop();

    let idx = 0;

    while (true) {
      let best = idx; // '가장 작은'이 아니라 '가장 우선인'
      const left = idx * 2 + 1;
      const right = idx * 2 + 2;

      if (left < heap.length && this.compare(heap[left], heap[best]) < 0)
        best = left;
      if (right < heap.length && this.compare(heap[right], heap[best]) < 0)
        best = right;

      if (best === idx) break;

      [heap[idx], heap[best]] = [heap[best], heap[idx]];
      idx = best;
    }

    return top;
  }
}

변수 이름을 min에서 top으로, smallest에서 best로 바꾼 건 의미상의 정리.

이제 "가장 작은 값"이 아니라 "가장 우선순위 높은 값"을 찾는 것이니까.

기준이 여러 개일 때

프로그래머스 디스크 컨트롤러를 풀 때는 이런 비교 함수를 썼다.

function compare(a, b) {
  if (a[0] !== b[0]) return a[0] - b[0];
  if (a[1] !== b[1]) return a[1] - b[1];
  return a[2] - b[2];
}

compare(a, b) < 0이면 a가 b보다 우선순위가 높은 것으로 처리된다.

구조를 보면 1순위로 비교하고, 같으면 2순위로, 또 같으면 3순위로 내려간다.

if (a[0] !== b[0])에서 걸러지면 거기서 끝이고, 통과했다는 건 1순위가 동점이라는 뜻이니 다음 기준을 볼 자격이 생긴다.

마무리

JS에 내장 힙이 없는 건 여전히 불만이긴함.

→ 그럼 언어 바꾸던가

→ 할 말 없긴 해요