This repository was archived by the owner on Sep 7, 2025. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 44
Expand file tree
/
Copy pathpriorityQueue.js
More file actions
117 lines (106 loc) · 2.67 KB
/
priorityQueue.js
File metadata and controls
117 lines (106 loc) · 2.67 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
/**
* @author Rashik Ansar
*
* Implemntaion of priority queue
* Lower the priority value higher its priority
* under the hood its implementing minBinaryHeap
*/
class PriorityQueue {
constructor() {
this.values = [];
}
/**
* Adding data to the queue
* @param {*} data Data to add into queue
* @param {*} priority Priority of the data
* @returns {PriorityQueue}
*/
enqueue(data, priority) {
let temp = new Node(data, priority);
this.values.push(temp);
this.bubbleUp();
return this;
}
/**
* removing a node from the queue
* @returns {Node}
*/
dequeue() {
const min = this.values[0];
const end = this.values.pop();
if (this.values.length > 0) {
this.values[0] = end;
this.sinkDown();
}
return min;
}
/**
* enqueue helper function
*/
bubbleUp() {
let index = this.values.length - 1;
const element = this.values[index];
while (index > 0) {
let parentIndex = Math.floor((index - 1) / 2);
let parent = this.values[parentIndex];
// if (element.priority <= parent.priority) break; //maxBinaryHeap condition
if (element.priority >= parent.priority) break; //minBinaryHeap condition
this.values[parentIndex] = element;
this.values[index] = parent;
index = parentIndex;
}
}
/**
* dequeue helper function
*/
sinkDown() {
let index = 0;
const length = this.values.length;
const element = this.values[index];
while (true) {
let leftChildIndex = 2 * index + 1;
let rightChildIndex = 2 * index + 2;
let leftChild;
let rightChild;
let swap = null;
if (leftChildIndex < length) {
leftChild = this.values[leftChildIndex];
// Change below comparision operators to make maxBinaryHeap
if (leftChild.priority < element.priority) {
swap = leftChildIndex;
}
}
if (rightChildIndex < length) {
rightChild = this.values[rightChildIndex];
// Change below comparision operators to make maxBinaryHeap
if (
(!swap && rightChild.priority < element.priority) ||
(swap && rightChild.priority < leftChild.priority)
) {
swap = rightChildIndex;
}
}
if (!swap) break;
this.values[index] = this.values[swap];
this.values[swap] = element;
index = swap;
}
}
}
class Node {
constructor(data, priority) {
this.data = data;
this.priority = priority;
}
}
let a = new PriorityQueue();
a.enqueue('Common Cold', 10);
a.enqueue('Gunshot wound', 2);
a.enqueue('Fever', 8);
console.log(a);
a.dequeue();
console.log(a);
a.dequeue();
console.log(a);
a.dequeue();
console.log(a);