[JS] 우선순위 큐(Priority Queue)와 힙(Heap) 구현

힙 (Heap)

 

힙은 트리 기반의 자료구조로, 완전 이진 트리 자료구조 (마지막 레벨을 제외하고 모든 레벨이 채워져있으며, 마지막 레벨은 왼쪽부터 채우는 트리 구조)이다. 또한, 힙은 최소 힙(Min Heap)과 최대 힙(Max Heap)으로 구성되는데, 최대 힙은 부모 노드가 항상 자식 노드보다 값이 커야 하며, 최소 힙은 반대로 부모 노드가 항상 자식 노드보다 값이 작아야 한다.

 

# 힙의 인덱스 관계

좌측 자식 노드의 인덱스 = 부모 노드의 인덱스 * 2 + 1
우측 자식 노드의 인덱스 = 부모 노드의 인덱스 * 2 + 2
부모 노드의 인덱스 = (자식 노드의 인덱스 - 1) // 2

 

우선순위 큐 (Priority Queue)

우선순위 큐란 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조로, 다익스트라 알고리즘 등에서 주로 사용된다. 파이썬에서는 heapq를 import하여 사용할 수 있지만, JS에서 사용하려면 직접 구현해야 한다...

 

 

JS로 Min Heap 구현하기

1. 기본 설정

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

  // 부모&자식 노드의 인덱스를 구하는 메서드
  getParent(index) {
    return Math.floor((index - 1) / 2);
  }
  getLeft(index) {
    return index * 2 + 1;
  }
  getRight(index) {
    return index * 2 + 2;
  }

}

 

2. enqueue

heappush(item) {
    this.heap.push(item);
    let current = this.heap.length - 1;

    // 현재 노드가 부모 노드보다 작으면 자리 바꿈
    while (this.heap[current] < this.heap[this.getParent(current)]) {
      let parent = this.getParent(current);

      [this.heap[parent], this.heap[current]] = [
        this.heap[current],
        this.heap[parent],
      ];

      current = parent;
    }

    this.heap[current] = item;
  }

 

3. dequeue

 heappop() {
    if (this.heap.length === 0) return undefined;

    // Return할 Root Node의 값을 저장 후 남은 값 재정렬
    const rootNode = this.heap[0];

    if (this.heap.length === 1) {
      this.heap = [];
    } else if (this.heap.length > 1) {
      // Heap의 마지막 노드를 RootNode에 등록 후 정렬
      this.heap[0] = this.heap.pop();
      let current = 0;

      // 자식 노드가 있는 동안 반복
      while (this.getLeft(current) < this.heap.length) {
        let left = this.getLeft(current);
        let right = this.getRight(current);
        let smaller =
          right < this.heap.length && this.heap[right] < this.heap[left]
            ? right
            : left;

        if (this.heap[current] > this.heap[smaller]) {
          // 좌우 노드의 값 비교 후 더 값이 작은 노드와 위치를 바꾼다
          [this.heap[current], this.heap[smaller]] = [
            this.heap[smaller],
            this.heap[current],
          ];
        } else break;

        current = smaller;
      }
    }

    return rootNode;
  }

 

4. 결과 테스트

const heap = new Heap();

for (let i = 10; i > 0; i--) {
  heap.heappush(i);
}

console.log(heap.heap); // [ 1, 2,  5, 4, 3, 9, 6, 10, 7, 8 ]

const result = [];

for (let i = 0; i < 10; i++) {
  const pop = heap.heappop();
  result.push(pop);
}

console.log(result); // [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]