-
Notifications
You must be signed in to change notification settings - Fork 0
/
PriorityQueue.js
81 lines (62 loc) · 1.95 KB
/
PriorityQueue.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
class Heap {
constructor() {
this.heap = [];
}
dangerouslyGetHeap = () => this.heap; // NOTE: 테스트용입니다. 실제로는 있어선 안 됩니다.
getLeftChildIndex = (parentIndex) => parentIndex * 2 + 1;
getRightChildIndex = (parentIndex) => parentIndex * 2 + 2;
getParentIndex = (childIndex) => parseInt((childIndex - 1) / 2);
getRoot = () => this.heap[0];
isEmpty = () => this.heap.length === 0;
remove = () => {
const root = this.getRoot();
if (this.heap.length > 1) {
this.heap[0] = this.heap.pop();
this.heapifyDown();
} else {
this.heap = [];
}
return root;
};
heapifyUp = () => {
let index = this.heap.length - 1;
const lastInsertedNode = this.heap[index];
while (index > 0) {
const parentIndex = this.getParentIndex(index);
if (lastInsertedNode.priority < this.heap[parentIndex].priority) {
this.heap[index] = this.heap[parentIndex];
index = parentIndex;
} else break;
}
this.heap[index] = lastInsertedNode;
};
heapifyDown = () => {
const rootNode = this.getRoot();
let index = 0;
while (this.getLeftChildIndex(index) < this.heap.length) {
const leftChildIndex = this.getLeftChildIndex(index);
const rightChildIndex = this.getRightChildIndex(index);
const smallestChildIndex =
rightChildIndex < this.heap.length &&
leftChildIndex.priority < rightChildIndex.priority
? rightChildIndex
: leftChildIndex;
if (this.heap[smallestChildIndex].priority <= rootNode.priority) {
this.heap[index] = this.heap[smallestChildIndex];
index = smallestChildIndex;
} else break;
}
this.heap[index] = rootNode;
};
}
class PriorityQueue extends Heap {
constructor() {
super();
}
enqueue = (priority, value) => {
this.heap.push({ priority, value });
this.heapifyUp();
};
dequeue = () => this.remove();
}
module.exports = PriorityQueue;