Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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
Add Comment
Please, Sign In to add comment