자바스크립트로 최소 힙(Min Heap) 구현하기

min-heap data structure

이진 트리를 기반으로 한 자료구조

부모 노드가 자식들보다 작거나 같은 구조
가장 작은 값이 부모 노드에 위치하는 자료구조

 

우선순위 큐 구현, Heap Sort에도 활용된다.
가장 작은 값을 `O(1)`의 시간으로 빠르게 찾을 수 있다는 장점이 있다.

 

다음은 자바스크립트로 최소 힙을 구현하는 코드이다.

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

  push(value) {
    this.heap.push(value);
    this.heapifyUp();
  }

  pop() {
    if (this.isEmpty()) return null;

    const root = this.heap[0];
    const lastNode = this.heap.pop();

    if (!this.isEmpty()) {
      this.heap[0] = lastNode;
      this.heapifyDown();
    }

    return root;
  }

  isEmpty() {
    return this.heap.length === 0;
  }

  heapifyUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[parentIndex] <= this.heap[index]) break;
      [this.heap[parentIndex], this.heap[index]] = [
        this.heap[index],
        this.heap[parentIndex],
      ];
      index = parentIndex;
    }
  }

  heapifyDown() {
    let index = 0;
    const length = this.heap.length;

    while (true) {
      let smallest = index;
      const leftChildIndex = 2 * index + 1;
      const rightChildIndex = 2 * index + 2;

      if (
        leftChildIndex < length &&
        this.heap[leftChildIndex] < this.heap[smallest]
      ) {
        smallest = leftChildIndex;
      }

      if (
        rightChildIndex < length &&
        this.heap[rightChildIndex] < this.heap[smallest]
      ) {
        smallest = rightChildIndex;
      }

      if (smallest === index) break;

      [this.heap[index], this.heap[smallest]] = [
        this.heap[smallest],
        this.heap[index],
      ];
      index = smallest;
    }
  }
}

1. heapifyUp()

코드에는 push()와 pop()이 먼저 구현되어 있지만, 이 두 메소드는 heapifyUp()과 heapifyDown()에 대한 이해가 선행되어야 하기 때문에 이 둘을 먼저 다뤄봐야겠다.

 

heapifyUp() 메소드는 새로 들어온 노드가 최소 힙의 조건에 맞는 자리를 찾도록 도와주는 메소드이다.

  heapifyUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[parentIndex] <= this.heap[index]) break;
      [this.heap[parentIndex], this.heap[index]] = [
        this.heap[index],
        this.heap[parentIndex],
      ];
      index = parentIndex;
    }
  }

따라서 새로 들어온 값의 자리 (this.heap.length - 1)부터 시작하여 index의 값이 0이 될 때까지(= 부모노드가 될 때까지) 그의 부모 노드 Math.floor(index - 1) / 2 와의 비교를 반복한다.
이진 트리의 특성 상 부모 노드가 자식들보다 값이 더 작거나 같아야하므로 이미 부모 노드가 현재 노드보다 값이 작거나 같다면 반복문을 종료한다.
만약 그렇지 않다면 swap을 진행하고 현재 값의 index를 parentIdx로 업데이트하며 과정을 반복한다.

부모 노드와 자식 노드의 인덱스 구하기

인덱스 i가 주어졌을 때 왼쪽 자식은 2 * i + 1에 위치하고, 오른쪽 자식은 2 * i + 2에 위치한다.
그러면 부모 노드는 반대로 자식 노드 인덱스 - 1 / 2에 위치하게 된다.

               10
            /      \
          20       30
         /  \      /
       40   50   100

여기 [10, 20, 30, 40, 50, 100]의 힙이 있다.
인덱스 4에 위치한 요소 50의 부모를 찾아보려고 한다.
4 - 1 / 2를 하면 1.5가 되고, 내림하면 1이 되어 부모의 값이 20임을 알 수 있다.

2. heapifyDown()

heapifyUp()이 새로 들어온 노드의 자리를 찾아주는 것이었다면, heapifyDown()은 루트 노드를 제거한 후 최소 힙의 조건에 맞도록 힙을 재정비하는 메소드이다.

  heapifyDown() {
    let index = 0;
    const length = this.heap.length;

    while (true) {
      let smallest = index;
      const leftChildIndex = 2 * index + 1;
      const rightChildIndex = 2 * index + 2;

      if (
        leftChildIndex < length &&
        this.heap[leftChildIndex] < this.heap[smallest]
      ) {
        smallest = leftChildIndex;
      }

      if (
        rightChildIndex < length &&
        this.heap[rightChildIndex] < this.heap[smallest]
      ) {
        smallest = rightChildIndex;
      }

      if (smallest === index) break;

      [this.heap[index], this.heap[smallest]] = [
        this.heap[smallest],
        this.heap[index],
      ];
      index = smallest;
    }
  }

루트 노드가 빠져나갔으므로 탐색을 0번 인덱스부터 시작한다.
왼쪽 자식 노드와 오른쪽 자식 노드의 인덱스를 찾고 부모 노드와 두 자식 노드 간의 비교를 수행한다.

초기값을 0으로 갖는 smallest라는 변수를 만들고, 조건에 따라 그 변수에 자식 노드의 인덱스 값을 할당한다.
이 smallest 변수는 자식 노드들과의 비교를 수행한 후에 밑에서 index의 노드와 서로 swap하게 된다.

 

leftChildIndex가 length보다 작고 (=범위를 벗어나지 않고) 왼쪽 자식 노드의 값이 부모 노드의 값보다 더 작다면 부모가 더 작아야하는 최소 힙의 성질을 만족하지 않으므로 둘을 바꾸기 위해 smallest에 leftChildIndex를 할당한다.

 

마찬가지로 rightChildIndex가 length보다 작고 오른쪽 자식 노드의 값이 부모 노드의 값보다 더 작다면 smallest에 rightChildIndex를 할당한다.

 

smallest가 index와 같다면 성질을 만족하는 것이므로 반복문을 종료한다.

반복문이 종료되지 않았다면 가장 작은 값으로 지정된 smallest와 초기 인덱스 값 index 간의 swap을 진행하고, index를 smallest로 업데이트해준다.
이 과정을 smallest와 index가 같아질 때까지, 더 이상 자신보다 큰 값이 부모 노드에 있지 않을 때까지 반복한다.

3. push(value)

힙에 값을 삽입하는 메소드이다.

  push(value) {
    this.heap.push(value);
    this.heapifyUp();
  }

힙은 배열로 구현되어 있고, 배열의 push 연산을 이용하고 있기 때문에 값이 맨 끝에 추가된다.
추가한 후 최소 힙의 성질을 만족할 수 있도록 마지막에 삽입된 요소를 끌어올려주는 heapifyUp()을 수행해준다.

4. pop()

힙의 루트 노드를 제거하는 메소드이다.

  pop() {
    if (this.isEmpty()) return null;

    const root = this.heap[0];
    const lastNode = this.heap.pop();

    if (!this.isEmpty()) {
      this.heap[0] = lastNode;
      this.heapifyDown();
    }

    return root;
  }

이미 힙이 비어있는 상태라면 null을 리턴한다.
루트 노드를 저장해둔다.
배열의 pop 연산을 수행한 후 그 값을 lastNode 변수에 저장해둔다.
힙이 비어있지 않다면 힙의 0번 인덱스(=부모 노드)에 lastNode의 값을 할당하고 힙의 성질을 만족할 수 있도록 heapifyDown()을 수행한다.
힙이 비어있지 않음을 체크하는 이유는 힙에 노드가 하나만 있는 경우도 있을 수 있기 때문이다.
마지막으로 저장해뒀던 루트 노드를 리턴한다.

5. isEmpty()

힙이 비어있지 않은지 확인하는 메소드이다. 불리언값을 리턴한다.

  isEmpty() {
    return this.heap.length === 0;
  }

 

같이 읽어보면 좋을 글

JavaScript로 Heap | Priority Queue 구현하기

힙에는 최소 힙과 최대 힙이 있는데 우선은 최소 힙을 먼저 다뤄보았다. 

최소 힙은 우선순위 큐를 구현하려면 필수적으로 알고 있어야 하는 개념인데, 이 우선순위 큐는 다익스트라 알고리즘을 구현할 때 쓰이기 때문에 최소 힙부터 제대로 이해하고 넘어가는 것이 중요한 것 같다. 

 

최소 힙을 이용하는 백준 문제: 1715 - 카드 정렬하기