-
-
Notifications
You must be signed in to change notification settings - Fork 61
/
PriorityQueue.ts
159 lines (157 loc) · 4.22 KB
/
PriorityQueue.ts
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
import { Base, initContainer } from '@/container/ContainerBase';
class PriorityQueue<T> extends Base {
/**
* @internal
*/
private readonly _priorityQueue: T[];
/**
* @internal
*/
private readonly _cmp: (x: T, y: T) => number;
/**
* @description PriorityQueue's constructor.
* @param container Initialize container, must have a forEach function.
* @param cmp Compare function.
* @param copy When the container is an array, you can choose to directly operate on the original object of
* the array or perform a shallow copy. The default is shallow copy.
*/
constructor(
container: initContainer<T> = [],
cmp: (x: T, y: T) => number =
(x: T, y: T) => {
if (x > y) return -1;
if (x < y) return 1;
return 0;
},
copy = true
) {
super();
this._cmp = cmp;
if (Array.isArray(container)) {
this._priorityQueue = copy ? [...container] : container;
} else {
this._priorityQueue = [];
container.forEach(element => this._priorityQueue.push(element));
}
this._length = this._priorityQueue.length;
const halfLength = this._length >> 1;
for (let parent = (this._length - 1) >> 1; parent >= 0; --parent) {
this._pushDown(parent, halfLength);
}
}
/**
* @internal
*/
private _pushUp(pos: number) {
const item = this._priorityQueue[pos];
while (pos > 0) {
const parent = (pos - 1) >> 1;
const parentItem = this._priorityQueue[parent];
if (this._cmp(parentItem, item) <= 0) break;
this._priorityQueue[pos] = parentItem;
pos = parent;
}
this._priorityQueue[pos] = item;
}
/**
* @internal
*/
private _pushDown(pos: number, halfLength: number) {
const item = this._priorityQueue[pos];
while (pos < halfLength) {
let left = pos << 1 | 1;
const right = left + 1;
let minItem = this._priorityQueue[left];
if (
right < this._length &&
this._cmp(minItem, this._priorityQueue[right]) > 0
) {
left = right;
minItem = this._priorityQueue[right];
}
if (this._cmp(minItem, item) >= 0) break;
this._priorityQueue[pos] = minItem;
pos = left;
}
this._priorityQueue[pos] = item;
}
clear() {
this._length = 0;
this._priorityQueue.length = 0;
}
/**
* @description Push element into a container in order.
* @param item The element you want to push.
*/
push(item: T) {
this._priorityQueue.push(item);
this._pushUp(this._length);
this._length += 1;
}
/**
* @description Removes the top element.
*/
pop() {
if (!this._length) return;
const last = this._priorityQueue.pop() as T;
this._length -= 1;
if (this._length) {
this._priorityQueue[0] = last;
this._pushDown(0, this._length >> 1);
}
}
/**
* @description Accesses the top element.
*/
top() {
return this._priorityQueue[0] as (T | undefined);
}
/**
* @description Check if element is in heap.
* @param item The item want to find.
* @return Boolean about if element is in heap.
*/
find(item: T) {
return this._priorityQueue.indexOf(item) >= 0;
}
/**
* @description Remove specified item from heap.
* @param item The item want to remove.
* @return Boolean about if remove success.
*/
remove(item: T) {
const index = this._priorityQueue.indexOf(item);
if (index < 0) return false;
if (index === 0) {
this.pop();
} else if (index === this._length - 1) {
this._priorityQueue.pop();
this._length -= 1;
} else {
this._priorityQueue.splice(index, 1, this._priorityQueue.pop() as T);
this._length -= 1;
this._pushUp(index);
this._pushDown(index, this._length >> 1);
}
return true;
}
/**
* @description Update item and it's pos in the heap.
* @param item The item want to update.
* @return Boolean about if update success.
*/
updateItem(item: T) {
const index = this._priorityQueue.indexOf(item);
if (index < 0) return false;
this._pushUp(index);
this._pushDown(index, this._length >> 1);
return true;
}
/**
* @return Return a copy array of heap.
*/
toArray() {
return [...this._priorityQueue];
}
}
export default PriorityQueue;