-
Notifications
You must be signed in to change notification settings - Fork 1
/
Priority Queue.js
81 lines (75 loc) · 2.02 KB
/
Priority Queue.js
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
//Priority Queue
class Node {
constructor(value, priority) {
this.value = value;
this.priority = priority;
}
}
class PriorityQueue {
constructor() {
this.values = [];
}
Enqueue(Value, priority) {
var newNode = new Node(Value, priority);
this.values.push(newNode);
this.bubbleUp();
return newNode;
}
//Helper Method
bubbleUp() {
var idx = this.values.length - 1;
while (idx > 0) {
let ParentIdx = Math.floor((idx - 1) / 2);
let parent = this.values[ParentIdx];
let element = this.values[idx];
if (element.priority < parent.priority) {
this.values[ParentIdx] = element;
this.values[idx] = parent;
idx = ParentIdx;
} else {
break;
}
}
}
dequeue() {
if (this.values.length === 0) return null;
if (this.values.length === 1) {
return this.values.pop();
}
let removed = this.values[0];
this.values[0] = this.values.pop();
let newEle = this.values[0];
let idx = 0;
let swaped = true;
let leftIdx;
let rightIdx;
while (swaped) {
leftIdx = 2 * idx + 1;
rightIdx = 2 * idx + 2;
if (leftIdx >= this.values.length || rightIdx >= this.values.length) {
swaped = false;
} else if (
newEle.priority > this.values[leftIdx].priority &&
this.values[rightIdx].priority < this.values[leftIdx].priority
) {
this.values[idx] = this.values[rightIdx];
this.values[rightIdx] = newEle;
idx = rightIdx;
} else if (
newEle.priority > this.values[leftIdx].priority &&
this.values[leftIdx].priority < this.values[rightIdx].priority
) {
this.values[idx] = this.values[leftIdx];
this.values[leftIdx] = newEle;
idx = leftIdx;
} else if (newEle.priority > this.values[rightIdx].priority) {
this.values[idx] = this.values[rightIdx];
this.values[rightIdx] = newEle;
idx = rightIdx;
} else {
swaped = false;
}
}
return removed;
}
}