Node.js 알고리즘에 사용할 우선순위큐 만들기

 

최단거리 알고리즘을 풀게 되면서 한 지점에서 다른 모든 지점에 대한 최단거리를 구할 때, 다익스트라 알고리즘사용한다는 사실을 알게 되었습니다.

 

다익스트라 알고리즘의 동작원리는

1. 출발 노드를 설정

2. 최단 거리 테이블을 초기화

3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택

4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신 혹은 우선순위 큐에 삽입

5. 위 과정에서 3번과 4번을 반복

 

이때 왜 우선순위큐를 사용하냐면

출처 : 패캠 초격차 나동빈님 강의

 

그렇게에 강의에서는 우선순위 큐를 사용하는 것을 추천해 주었는데, 자바스크립트에서는 다른 언어와 달리 우선순위 큐가 내장되어 있지 않습니다.  대신 아래에 있는 누군가 구현한 코드를 활용해서 알고리즘을 풀면 된다고 했는데, 이 코드를 해석해보려고 합니다

https://github.com/janogonzalez/priorityqueuejs/blob/master/index.js

 

/**
 * Expose `PriorityQueue`.
 */
module.exports = PriorityQueue;

/**
 * Initializes a new empty `PriorityQueue` with the given `comparator(a, b)`
 * function, uses `.DEFAULT_COMPARATOR()` when no function is provided.
 *
 * The comparator function must return a positive number when `a > b`, 0 when
 * `a == b` and a negative number when `a < b`.
 *
 * @param {Function}
 * @return {PriorityQueue}
 * @api public
 */
function PriorityQueue(comparator) {
  this._comparator = comparator || PriorityQueue.DEFAULT_COMPARATOR;
  this._elements = [];
}

/**
 * Compares `a` and `b`, when `a > b` it returns a positive number, when
 * it returns 0 and when `a < b` it returns a negative number.
 *
 * @param {String|Number} a
 * @param {String|Number} b
 * @return {Number}
 * @api public
 */
PriorityQueue.DEFAULT_COMPARATOR = function(a, b) {
  if (typeof a === 'number' && typeof b === 'number') {
    return a - b;
  } else {
    a = a.toString();
    b = b.toString();

    if (a == b) return 0;

    return (a > b) ? 1 : -1;
  }
};

/**
 * Returns whether the priority queue is empty or not.
 *
 * @return {Boolean}
 * @api public
 */
PriorityQueue.prototype.isEmpty = function() {
  return this.size() === 0;
};

/**
 * Peeks at the top element of the priority queue.
 *
 * @return {Object}
 * @throws {Error} when the queue is empty.
 * @api public
 */
PriorityQueue.prototype.peek = function() {
  if (this.isEmpty()) throw new Error('PriorityQueue is empty');

  return this._elements[0];
};

/**
 * Dequeues the top element of the priority queue.
 *
 * @return {Object}
 * @throws {Error} when the queue is empty.
 * @api public
 */
PriorityQueue.prototype.deq = function() {
  var first = this.peek();
  var last = this._elements.pop();
  var size = this.size();

  if (size === 0) return first;

  this._elements[0] = last;
  var current = 0;

  while (current < size) {
    var largest = current;
    var left = (2 * current) + 1;
    var right = (2 * current) + 2;

    if (left < size && this._compare(left, largest) >= 0) {
      largest = left;
    }

    if (right < size && this._compare(right, largest) >= 0) {
      largest = right;
    }

    if (largest === current) break;

    this._swap(largest, current);
    current = largest;
  }

  return first;
};

/**
 * Enqueues the `element` at the priority queue and returns its new size.
 *
 * @param {Object} element
 * @return {Number}
 * @api public
 */
PriorityQueue.prototype.enq = function(element) {
  var size = this._elements.push(element);
  var current = size - 1;

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

    if (this._compare(current, parent) <= 0) break;

    this._swap(parent, current);
    current = parent;
  }

  return size;
};

/**
 * Returns the size of the priority queue.
 *
 * @return {Number}
 * @api public
 */
PriorityQueue.prototype.size = function() {
  return this._elements.length;
};

/**
 *  Iterates over queue elements
 *
 *  @param {Function} fn
 */
PriorityQueue.prototype.forEach = function(fn) {
  return this._elements.forEach(fn);
};

/**
 * Compares the values at position `a` and `b` in the priority queue using its
 * comparator function.
 *
 * @param {Number} a
 * @param {Number} b
 * @return {Number}
 * @api private
 */
PriorityQueue.prototype._compare = function(a, b) {
  return this._comparator(this._elements[a], this._elements[b]);
};

/**
 * Swaps the values at position `a` and `b` in the priority queue.
 *
 * @param {Number} a
 * @param {Number} b
 * @api private
 */
PriorityQueue.prototype._swap = function(a, b) {
  var aux = this._elements[a];
  this._elements[a] = this._elements[b];
  this._elements[b] = aux;
};

 

 

위의 코드를 이해하기에 앞서 힙(heap)이라는 자료구조를 알 필요가 있습니다.

 

힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조로서 

• A가 B의 부모노드(parent node) 이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다.

이때 부모가 자식보다 크면 최대 힙, 작으면 최소 힙이라고 한다. (출처 : 위키백과)

아래와 같은 구조는 최대 힙이다. 

이를 통해서 부모노드는 항상 자식보다 큰 값을 가지며, 우리는 추상적 자료구조인 우선순위큐를 구현할 수 있다.

 

출처 : 위키 백과

 

 

 

 

 

최대힙에서 삽입

만약 추가적인 자료가 삽입된다면, 우선 마지막 노드 위치에 추가되고, 부모 노드와 비교하여 최대힙 조건이 만족될 떄까지 이동한다. 그렇기 때문에 배열에 단순히 추가하는 것은 O(1) 이지만 최대 힙에서 시간복잡도는 O(log(N))이다

최대힙에서 삭제

최대힙에서 삭제할 때는, 부모 노드를 제거한다 .

이후 마지막 노드를 부모로 이동시킨 후, 두 값 중에서 더 큰 값을 가진 노드와 스왑을 진행하여, 최대 힙이 만족될 떄까지 정렬한다.

 

 

이제 힙에 대한 설명이 끝났으니, 다시 위의 코드에 대한 분석을 해보자. 결국 우리의 목적은 알고리즘(백준?)에 쓸 우선순위 큐를 만드는 것이고, 위의 코드는 라이브러리 형식이기에 모듈로 export 되어있다. 라이브러리 기에 기본적인 우선순위 큐를 설정해두었고, 외부에서 비교로직을 준다면 해당 로직으로 사용한다. 따라서 우리는 위의 코드를 아래와 같이 수정할 수 있다. (불필요한 주석 제거)

 

1. 외부에서 무조건 comparator를 전달하는 구조를 만들자.

function PriorityQueue(comparator) {
  this._comparator = comparator
  this._elements = [];
}

 

2. isEmpty 와 peek , size

size는 elements의 길이를 측정해준다. elements에 저장된 노드를 담긴 때문에 해당 배열의 길이가 우선순위큐의 크기다.

isEmpty는 큐가 비었는지 확인하는 함수이다. 따라서  ;size가 0이면 비었있다'라고 구현했다.

peek의 경우 가장 먼저 제거되는 녀석(부모 노드)를 알려주면 된다. 이는 elements라는 배열의 0번째 인덱스 값이다.

function PriorityQueue(comparator) {
  this._comparator = comparator 
  this._elements = [];
}


PriorityQueue.prototype.isEmpty = function() {
  return this.size() === 0;
};


PriorityQueue.prototype.peek = function() {
  if (this.isEmpty()) throw new Error('PriorityQueue is empty');

  return this._elements[0];
};


PriorityQueue.prototype.size = function() {
  return this._elements.length;
};

3. forEach, swap, compare 

우선순위를 정해서 삽입 및 추가하려면, 기존 노드들을 비교, 스왑할 필요가 있다고 했다.

forEach: 큐 내의 elements에 대해서 배열의 forEach 메서드 실행 (  fn을 통해 함수를 매개변수로 받어 콜백함수로 사용)

compare :forEach노드에 사용할 비교함수. 각각의 노드를 comparator를 활용해서 비교함

swap : aux에 a 를 잠시 저장하고, b를 a에 할당, b에 aux를 할당함으로서 a와 b를 교체함

PriorityQueue.prototype.forEach = function(fn) {
  return this._elements.forEach(fn);
};


PriorityQueue.prototype._compare = function(a, b) {
  return this._comparator(this._elements[a], this._elements[b]);
};

PriorityQueue.prototype._swap = function(a, b) {
  var aux = this._elements[a];
  this._elements[a] = this._elements[b];
  this._elements[b] = aux;
};

 

4. enq와 deq  (삽입과 제거)

이제 내부 프로토타입들은 완성 되었으므로, 이를 활용하여 deq와 enq  프토로타입을 만들면 됩니다.

PriorityQueue.prototype.enq = function(element) {
  var size = this._elements.push(element);
  var current = size - 1;

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

    if (this._compare(current, parent) <= 0) break;

    this._swap(parent, current);
    current = parent;
  }

  return size;
};

 

위쪽 위키백과 이미지에 배열 테이블을 보시면 한 하위노드에 대한 부모노드의 취니는 해당 노드의 인덱스/2를 내림 한 값과 같습니다. 따라서 부모 노드를 찾고, 비교했을 때, 현재값이 작거나 같다면 멈추고, 아니면 swap을 계속 진행해줍니다.

이후 현재값을 parent노드 값(기존에 삽입한 값)으로 변경 후  해당 위치에서는 힙구조(최대인지 최소인지)에 맞는 위치인지를 확인합니다. 맞다면 변경된 size를 반환합니다.

 

PriorityQueue.prototype.deq = function() {
  var first = this.peek();
  var last = this._elements.pop();
  var size = this.size();

  if (size === 0) return first;

  this._elements[0] = last;
  var current = 0;

  while (current < size) {
    var largest = current;
    var left = (2 * current) + 1;
    var right = (2 * current) + 2;

    if (left < size && this._compare(left, largest) >= 0) {
      largest = left;
    }

    if (right < size && this._compare(right, largest) >= 0) {
      largest = right;
    }

    if (largest === current) break;

    this._swap(largest, current);
    current = largest;
  }

  return first;
};

1. 부모노드의 값을 first에 담아주고, 마지막 값을 추출해서 last에 할당합니다.

(size가 0이면 추출이 안되므로 에러가 뜨고 아니라면  first는 root 노드의 값)

2.  elements 배열에 마지막 자식 노드를 할당합니다 ( 부모노드 덮어씌워지기 떄문에 first에 미리 할당하는 것입니다.)

그리고 해당 index는 0이기에 current에 0을 할당합니다.

3. while문 안에서, 인덱스를 통해서 자식 노드의 위치를 찾습니다.  이때 현재 위치가 사이즈보단 작아야함으로 이를 조건에넣습니다.

4. 만약 자식 노드 중 왼쪽과 오른쪽이 size보다 작으면서 비교결과가 크다면 largest의 값을 해당 인덱스로 할당해줍니다. 

5. largest가 current랑 같다는건 교체되지 않았다는 것이므로 while문을 멈추고, 그렇지 않다면 swap을 통해 현재값과 largest값을 swap하고, 해당인덱스에 대해서 다시  비교를 합니다.

 

 

알고리즘 테스트에 사용할 최종코드는 아래와 같습니다. ( 주석은 제거하고 var => let으로 교체하였습니다)

function PriorityQueue(comparator) {
  this._comparator = comparator;
  this._elements = [];
}

PriorityQueue.prototype.isEmpty = function () {
  return this.size() === 0;
};

PriorityQueue.prototype.peek = function () {
  if (this.isEmpty()) throw new Error('PriorityQueue is empty');
  return this._elements[0];
};

PriorityQueue.prototype.deq = function () {
  let first = this.peek();
  let last = this._elements.pop();
  let size = this.size();

  if (size === 0) return first;

  this._elements[0] = last;
  let current = 0;

  while (current < size) {
    let largest = current;
    let left = 2 * current + 1;
    let right = 2 * current + 2;

    if (left < size && this._compare(left, largest) >= 0) {
      largest = left;
    }

    if (right < size && this._compare(right, largest) >= 0) {
      largest = right;
    }

    if (largest === current) break;

    this._swap(largest, current);
    current = largest;
  }

  return first;
};

PriorityQueue.prototype.enq = function (element) {
  let size = this._elements.push(element);
  let current = size - 1;

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

    if (this._compare(current, parent) <= 0) break;

    this._swap(parent, current);
    current = parent;
  }

  return size;
};

PriorityQueue.prototype.size = function () {
  return this._elements.length;
};

PriorityQueue.prototype.forEach = function (fn) {
  return this._elements.forEach(fn);
};

PriorityQueue.prototype._compare = function (a, b) {
  return this._comparator(this._elements[a], this._elements[b]);
};

PriorityQueue.prototype._swap = function (a, b) {
  let aux = this._elements[a];
  this._elements[a] = this._elements[b];
  this._elements[b] = aux;
};

 

 

 

 

사용 예시

function PriorityQueue(comparator) {
  this._comparator = comparator;
  this._elements = [];
}

PriorityQueue.prototype.isEmpty = function () {
  return this.size() === 0;
};

PriorityQueue.prototype.peek = function () {
  if (this.isEmpty()) throw new Error('PriorityQueue is empty');
  return this._elements[0];
};

PriorityQueue.prototype.deq = function () {
  let first = this.peek();
  let last = this._elements.pop();
  let size = this.size();

  if (size === 0) return first;

  this._elements[0] = last;
  let current = 0;

  while (current < size) {
    let largest = current;
    let left = 2 * current + 1;
    let right = 2 * current + 2;

    if (left < size && this._compare(left, largest) >= 0) {
      largest = left;
    }

    if (right < size && this._compare(right, largest) >= 0) {
      largest = right;
    }

    if (largest === current) break;

    this._swap(largest, current);
    current = largest;
  }

  return first;
};

PriorityQueue.prototype.enq = function (element) {
  let size = this._elements.push(element);
  let current = size - 1;

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

    if (this._compare(current, parent) <= 0) break;

    this._swap(parent, current);
    current = parent;
  }

  return size;
};

PriorityQueue.prototype.size = function () {
  return this._elements.length;
};

PriorityQueue.prototype.forEach = function (fn) {
  return this._elements.forEach(fn);
};

PriorityQueue.prototype._compare = function (a, b) {
  return this._comparator(this._elements[a], this._elements[b]);
};

PriorityQueue.prototype._swap = function (a, b) {
  let aux = this._elements[a];
  this._elements[a] = this._elements[b];
  this._elements[b] = aux;
};

 let pq = new PriorityQueue((a, b) => b[0] - a[0]);