Create a gist now

Instantly share code, notes, and snippets.

Embed
What would you like to do?
[priority-queue] a demo of priority queue #snippet
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment