힙

언제 쓰나

값이 계속 들어오고 빠지는 동안, 그때그때 가장 큰 값이나 가장 작은 값을 꺼내야 할 때 씁니다.

• “가장 무거운 두 개를 꺼내 합친 결과를 다시 넣는다”처럼 꺼내고 다시 넣는 일을 반복합니다. 한 번 정렬해 두는 것으로는 부족하고, 넣을 때마다 순서가 달라집니다.
• 작업이나 요청을 도착한 순서가 아니라 우선순위 순서로 처리합니다. 이렇게 우선순위가 가장 높은 값부터 꺼내는 큐를 우선순위 큐(priority queue)라고 부르고, 힙은 우선순위 큐를 만드는 가장 흔한 방법입니다.
• 다익스트라처럼 “아직 확정하지 않은 것 가운데 가장 가까운 것”을 반복해서 골라야 하는 알고리즘의 부품으로 들어갑니다.

JavaScript에는 힙이 내장되어 있지 않아서, 코딩 테스트에서는 아래 대표 문제 풀이의 MaxHeap처럼 직접 구현해야 합니다.

어떻게 동작하나

매번 가장 큰 값을 찾으면 느리다

LeetCode 1046은 돌 무게 배열 stones에서 가장 무거운 돌 두 개를 골라 부딪히는 일을 돌이 하나 이하로 남을 때까지 반복하는 문제입니다. 두 돌의 무게가 같으면 둘 다 없어지고, 다르면 무게 차이만큼의 돌 하나가 남습니다. 마지막에 남은 돌의 무게를 반환하고, 남은 돌이 없으면 0을 반환합니다.

stones = [2, 7, 4, 1, 8, 1]로 직접 해 보겠습니다.

1. 가장 무거운 8과 7을 부딪혀 1이 남습니다. 돌은 [2, 4, 1, 1, 1]이 됩니다.
2. 4와 2를 부딪혀 2가 남습니다. 돌은 [1, 1, 1, 2]가 됩니다.
3. 2와 1을 부딪혀 1이 남습니다. 돌은 [1, 1, 1]이 됩니다.
4. 1과 1은 무게가 같아 둘 다 없어집니다. 돌 [1] 하나가 남아 답은 1입니다.

매 라운드마다 배열 전체를 훑어 가장 무거운 두 돌을 찾으면 한 라운드에 O(n)이 들고, 라운드가 최대 n번이라 전체는 O(n²)입니다. 처음에 한 번 정렬해 두어도 2번 과정의 새 돌 2처럼 부딪히고 남은 돌이 중간 어딘가에 끼어들어야 해서, 순서를 다시 맞추는 비용이 매번 듭니다.

부모가 자식보다 크거나 같은 트리

힙은 “가장 큰 값 하나”만 늘 맨 위에 두고, 나머지는 느슨하게만 정리해 둡니다. 모든 값을 정렬하지 않으니 넣고 빼는 비용이 작습니다. 아래는 위 예제의 돌 여섯 개를 모두 넣은 힙입니다.

최대 힙 · heap = [null, 8, 7, 4, 1, 2, 1]

그림을 읽는 법은 이렇습니다.

• 위에서 아래로, 같은 층에서는 왼쪽에서 오른쪽으로 빈자리 없이 채운 트리입니다. 이런 트리를 완전 이진 트리(complete binary tree)라고 합니다.
• 모든 노드는 자기 자식보다 크거나 같습니다. 그래서 맨 위의 노드인 루트(root)가 전체에서 가장 큰 값입니다. 이 규칙을 지키는 힙을 최대 힙(max heap)이라고 부르고, 부등호를 반대로 두면 가장 작은 값이 루트에 오는 최소 힙이 됩니다.
• 형제끼리는 순서가 없습니다. 2번 노드 7과 3번 노드 4 가운데 어느 쪽이 커도 상관없고, 7 아래의 1이 4보다 작아도 규칙에 어긋나지 않습니다.
• 빈자리 없이 채웠으므로 트리를 배열 하나에 층 순서대로 담을 수 있습니다. 배열의 0번 칸은 비워 두고 루트를 1번 칸에 담으면, i번 칸의 자식은 2 * i번과 2 * i + 1번 칸이고 부모는 Math.floor(i / 2)번 칸입니다. 그림에서 2번 칸의 자식이 4번 칸과 5번 칸인 것과 같습니다.

자식은 왜 2i번과 2i + 1번인가

노드 번호는 위층부터, 같은 층에서는 왼쪽부터 1, 2, 3, …으로 붙입니다. 이 순서를 따라가면 식이 나옵니다.

1. 루트 1번의 자식은 바로 다음 번호인 2번과 3번입니다.
2. 2번의 자식은 1번의 자식 두 개 바로 뒤에 오니 4번과 5번이고, 3번의 자식은 그 뒤인 6번과 7번 자리입니다. 그림에는 6번까지만 찼습니다.
3. 노드마다 자식이 두 개씩 번호 순서대로 이어지므로, 부모 번호가 1 커질 때마다 왼쪽 자식 번호는 2씩 커집니다. 1번의 왼쪽 자식이 2번에서 시작하니, i번의 왼쪽 자식은 2 + 2 × (i − 1) = 2i번입니다. 오른쪽 자식은 그 바로 옆이라 2i + 1번입니다.

부모는 이 식을 거꾸로 씁니다. 왼쪽 자식 2i를 2로 나누면 i가 되고, 오른쪽 자식 2i + 1을 2로 나누면 i.5가 되는데 소수점을 버리면 역시 i입니다. 그래서 두 자식 모두 Math.floor(i / 2)로 같은 부모를 찾습니다. 그림의 5번 칸 2는 5 / 2 = 2.5를 내림한 2번 칸 7이 부모입니다.

0번 칸을 비워 두는 이유도 여기에 있습니다. 루트를 0번 칸에 두면 루트의 왼쪽 자식이 2 × 0 = 0번, 즉 자기 자신이 되어 식이 맞지 않습니다. 그래서 0번 칸부터 쓸 때는 번호를 하나씩 밀어 자식을 2 * i + 1, 2 * i + 2번, 부모를 Math.floor((i - 1) / 2)번으로 계산해야 합니다. 0번 칸 하나를 쓰지 않는 대신 식에서 1을 더하고 빼는 일이 없어집니다.

넣을 때는 올라가고, 꺼낼 때는 내려간다

값을 넣거나 꺼낸 뒤에도 “부모가 자식보다 크거나 같다”는 규칙이 지켜지도록, 규칙이 깨진 곳에서 이웃한 두 노드의 자리를 바꿉니다.

넣기

1. 새 값을 배열 맨 끝 칸에 붙입니다. 트리에서는 맨 아래층의 빈자리 가운데 가장 왼쪽입니다.
2. 새 값이 부모보다 크면 부모와 자리를 바꿉니다. 부모보다 크지 않거나 루트에 닿을 때까지 반복합니다.

꺼내기

1. 루트의 값을 꺼냅니다. 이 값이 가장 큰 값입니다.
2. 배열 맨 끝 칸의 값을 루트 자리로 옮깁니다. 빈자리 없이 채운 모양을 유지하려는 것입니다.
3. 옮긴 값이 두 자식 가운데 더 큰 자식보다 작으면 그 자식과 자리를 바꿉니다. 두 자식보다 크거나 같아지거나 맨 아래에 닿을 때까지 반복합니다.

꺼내기 3번에서 더 작은 자식과 바꾸면, 위로 올라온 작은 자식이 다른 쪽의 큰 자식을 자식으로 두게 되어 규칙이 깨집니다. 그래서 늘 더 큰 자식과 바꿉니다.

자리를 바꾸는 횟수는 트리의 높이를 넘지 않습니다. 노드가 n개인 완전 이진 트리의 높이는 log n 정도라서, 돌이 100만 개여도 한 번 넣거나 꺼낼 때 자리를 바꾸는 횟수는 20번 안쪽입니다. 넣기와 꺼내기가 모두 O(log n)이고, 가장 큰 값은 루트에 있으니 확인만 하는 데는 O(1)이 듭니다.

직접 따라가 보기

아래에서 “다음”을 누르면 2~7번째 단계에서 돌 여섯 개가 차례로 힙에 들어갑니다. 6번째 단계에서 8이 맨 끝에 붙은 뒤 부모 2, 7과 차례로 자리를 바꿔 루트까지 올라가는데, 파란 노드와 간선이 8이 지나온 길입니다. 8번째 단계에서는 루트의 8이 오른쪽 빨간 자리로 꺼내지고, 맨 끝의 1이 루트로 옮겨진 뒤 7, 2와 자리를 바꾸며 5번 칸까지 내려갑니다. 트리 아래의 배열 칸도 같은 색으로 바뀌니 트리와 배열이 같은 내용이라는 것을 함께 확인해 보세요.

처음부터 이전 자동 재생 다음

단계 1 / 19

최대 힙 · stones = [2, 7, 4, 1, 8, 1]

변수

y

–가장 무거운 돌

x

–두 번째로 무거운 돌

heap.size

0

result

–

빈 힙에서 시작합니다. 배열의 0번 칸은 비워 두고 1번 칸부터 씁니다. "다음"을 눌러 보세요

• 방금 넣거나 옮긴 값이 멈춘 자리
• 자리를 바꾸며 지나온 길
• 힙에 있는 값
• 남은 돌

대표 문제 풀이

아래는 참고 풀이입니다. MaxHeap의 ①②가 넣기, ③④⑤가 꺼내기 규칙이고, 변수 이름은 시각화의 변수 칸과 같습니다.

class MaxHeap {
  constructor() {
    // 0번 칸은 비워 두고 1번 칸부터 쓴다
    this.heap = [null];
  }

  get size() {
    return this.heap.length - 1;
  }

  push(value) {
    const heap = this.heap;
    // ① 맨 끝 칸에 붙인다
    heap.push(value);
    let i = heap.length - 1;
    while (i > 1) {
      const parent = Math.floor(i / 2);
      // ② 부모가 크거나 같으면 멈추고, 아니면 부모와 자리를 바꿔 올라간다
      if (heap[parent] >= heap[i]) break;
      [heap[parent], heap[i]] = [heap[i], heap[parent]];
      i = parent;
    }
  }

  pop() {
    const heap = this.heap;
    // ③ 루트(1번 칸)를 꺼낸다
    const top = heap[1];
    const last = heap.pop();
    if (heap.length > 1) {
      // ④ 맨 끝 값을 루트로 옮긴다
      heap[1] = last;
      let i = 1;
      while (i * 2 < heap.length) {
        const left = i * 2;
        const right = i * 2 + 1;
        let bigger = left;
        if (right < heap.length && heap[right] > heap[left]) bigger = right;
        // ⑤ 더 큰 자식보다 크거나 같으면 멈추고, 아니면 그 자식과 자리를 바꿔 내려간다
        if (heap[i] >= heap[bigger]) break;
        [heap[i], heap[bigger]] = [heap[bigger], heap[i]];
        i = bigger;
      }
    }
    return top;
  }
}

function lastStoneWeight(stones) {
  const heap = new MaxHeap();
  for (const stone of stones) heap.push(stone);

  while (heap.size > 1) {
    const y = heap.pop(); // 가장 무거운 돌
    const x = heap.pop(); // 두 번째로 무거운 돌
    if (y !== x) heap.push(y - x);
  }

  return heap.size === 1 ? heap.pop() : 0;
}

pop 안의 heap.pop()은 JavaScript 배열의 메서드로, 배열 맨 끝 칸의 값을 떼어 내 ④에서 루트로 옮길 값을 얻습니다. 힙에 값이 하나뿐이었다면 그 값이 곧 루트라서 떼어 낸 뒤 비워 둔 0번 칸만 남고(heap.length가 1), 옮길 곳이 없으니 if로 건너뜁니다. 내려가는 반복의 조건 i * 2 < heap.length는 왼쪽 자식이 있다는 뜻입니다. 왼쪽 자식이 없으면 오른쪽 자식도 없으니 맨 아래에 닿은 것입니다.

돌 n개를 넣는 데 O(n log n)이 들고, 반복 한 번마다 돌이 적어도 하나 줄어서 반복은 n번을 넘지 않습니다. 반복 한 번에 넣기와 꺼내기를 합쳐 세 번 이하로 하니 전체 시간은 O(n log n)이고, 공간은 힙 배열의 O(n)입니다.