🎯 우선순위 큐

우선순위 큐를 구현할 때 내부적으로 최소 힙 또는 최대 힙을 이용한다. 최소 힙을 이용하는 경우 ‘값이 가장 낮은 데이터가 먼저 삭제’되며, 최대 힙을 이용하는 경우 ‘값이 큰 데이터가 먼저 삭제’된다. 이때 힙은 삽입과 삭제에 O(NlogN)의 시간 복잡도를 가진다.

🎯 힙의 특징

힙의 부모와 자식 간에 다음과 같은 관계가 성립한다.

  • 왼쪽 자식의 index : 부모의 index * 2 + 1
  • 오른쪽 자식의 index : (부모의 index * 2) + 2
  • 부모의 index : Math.floor((자식의 index - 1) / 2)

🎯 삽입 연산 (bubbleUp)

Min Heap의 삽입 연산은 다음과 같은 단계로 이루어진다.

  1. Heap의 마지막 위치에 요소를 추가한다.
  2. 새로운 요소를 추가한 위치에서부터, 부모 노드와 새로 추가된 노드의 값을 비교한다. 만약 새로 추가된 노드의 값이 부모 노드의 값보다 작다면, 부모 노드와 새로 추가된 노드의 위치를 교환한다.
  3. 이전 단계에서 교환된 새로 추가된 노드와 부모 노드의 값 비교를 반복한다. 이 단계를 반복하여 Min Heap의 규칙을 지킨다.

bubbleUp의 코드는 아래와 같다.

add(value) {
  this.heap.push(value);
  this.bubbleUp();
}

bubbleUp() {
  let index = this.heap.length - 1;
  let parentIdx = Math.floor((index - 1) / 2);

  while(this.heap[parentIdx] && this.heap[index][1] < this.heap[parentIdx][1]) {
    this.swap(index, parentIdx);
    index = parentIdx;
    parentIdx = Math.floor((index - 1) / 2);
  }
}

🎯 삭제 연산 (bubbleDown)

Min Heap의 삭제 연산은 다음과 같은 단계로 이루어진다.

  1. Heap에서 가장 작은 값을 가진 노드(루트)를 제거한다.
  2. Heap의 맨 마지막에 있는 노드를 새로운 루트 노드로 이동시킨다.
  3. 새로운 루트 노드와 자식 노드의 값을 비교하여, 자식 노드의 값이 작다면 루트 노드의 위치를 교환한다.
  4. 이전 단계에서 교환된 새로 추가된 노드와 부모 노드의 값 비교를 반복한다. 이 단계를 반복하여 Min Heap의 규칙을 지킨다.

bubbleDown의 코드는 아래와 같다.

poll() {
  if(this.heap.length === 1) {
    return this.heap.pop();
  }

  const value = this.heap[0];
  this.heap[0] = this.heap.pop();
  this.bubbleDown();
  return value;
}

bubbleDown() {
  let index = 0;
  let leftIdx = index * 2 + 1;
  let rightIdx = index * 2 + 2;

  while((this.heap[leftIdx] && this.heap[leftIdx][1] < this.heap[index][1]) ||
       (this.heap[rightIdx] && this.heap[rightIdx][1] < this.heap[index][1])) {

    let smallIdx = leftIdx;

    if(this.heap[rightIdx] && this.heap[rightIdx][1] < this.heap[smallIdx][1]) {
      smallIdx = rightIdx;
    }

    this.swap(index, smallIdx);
    index = smallIdx;
    leftIdx = index * 2 + 1;
    rightIdx = index * 2 + 2;
  }
}

🎯 우선순위 큐 코드 구현 (JS)

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

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

  swap(idx1, idx2) {
    [this.heap[idx1], this.heap[idx2]] = [this.heap[idx2], this.heap[idx1]];
  }

  add(value) {
    this.heap.push(value);
    this.bubbleUp();
  }

  poll() {
    if(this.heap.length === 1) return this.heap.pop();

    const value = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown();
    return value;
  }

  bubbleUp() {
    let index = this.heap.length - 1;
    let parentIndex = Math.floor((index - 1) / 2);

    while(this.heap[parentIndex] && this.heap[parentIndex][1] > this.heap[index][1]) {
      this.swap(index, parentIndex);
      index = parentIndex;
      parentIndex = Math.floor((index - 1) / 2);
    }
  }

  bubbleDown() {
    let index = 0;
    let leftIndex = index * 2 + 1;
    let rightIndex = index * 2 + 2;

    while((this.heap[leftIndex] && this.heap[index][1] > this.heap[leftIndex][1]) || (this.heap[rightIndex] && this.heap[index][1] > this.heap[rightIndex])) {
      let smallIndex = leftIndex;

      if(this.heap[rightIndex][1] < this.heap[smallIndex][1]) {
        smallIndex = rightIndex;
      }

      this.swap(index, smallIndex);
      index = smallIndex;
      leftIndex = index * 2 + 1;
      rightIndex = index + 2 + 2;
    }
  }

📑 Reference

참돔 블로그 - 자바스크립트로 힙 구현하기