[priority-queue] a demo of priority queue #snippet

priority-queue.js

const PriorityQueue = function () {
  this.data = [];
};

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

PriorityQueue.prototype.less = function(i, j) {
  return this.data[i] < this.data[j];
};

PriorityQueue.prototype.swap = function (i, j) {
  let tmp = this.data[i];
  this.data[i] = this.data[j];
  this.data[j] = tmp;
};

PriorityQueue.prototype.enqueue = function (...ele) {
  this.data.push(...ele);
  this.data.unshift(null);
  for (let i = parseInt((this.data.length - 1) / 2); i >= 1; i--) {
    if (this.less(i, i * 2)) this.swap(i, i * 2);
    if (this.data[i * 2 + 1] !== undefined && this.less(i, i * 2 + 1)) this.swap(i, i * 2 + 1);
  }
  this.data.shift();
};

PriorityQueue.prototype.dequeue = function () {
  if (this.isEmpty()) return undefined;

  const result = this.data.shift();
  this.data = [null, this.data[this.data.length - 1], ...this.data.slice(0, this.data.length - 1)];
  for (let i = 1; i <= parseInt((this.data.length - 1) / 2);) {
    let j = 2 * i;
    if (j < this.data.length - 1 && this.less(j, j + 1)) j++;
    if (!this.less(i, j)) break;
    this.swap(i, j);
    i = j;
  }
  this.data.shift();
  return result;
};

const pq = new PriorityQueue();
pq.enqueue(1, 13, 3);
pq.enqueue(31, 3);
pq.enqueue(22);
console.log(pq.dequeue()); // 31
console.log(pq.dequeue()); // 22
console.log(pq.dequeue()); // 13
console.log(pq.dequeue()); // 3
console.log(pq.dequeue()); // 3
console.log(pq.dequeue()); // 1
console.log(pq.dequeue()); // undefined