/
fast-priority-queue.js
295 lines (272 loc) · 8.37 KB
/
fast-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
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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
/**
* FastPriorityQueue.js : a fast heap-based priority queue in JavaScript.
* (c) the authors
* Licensed under the Apache License, Version 2.0.
*
* Speed-optimized heap-based priority queue for modern browsers and JavaScript engines.
*
* Usage :
Installation (in shell, if you use node):
$ npm install fastpriorityqueue
Running test program (in JavaScript):
// var FastPriorityQueue = require("fastpriorityqueue");// in node
var x = new FastPriorityQueue();
x.add(1);
x.add(0);
x.add(5);
x.add(4);
x.add(3);
x.peek(); // should return 0, leaves x unchanged
x.size; // should return 5, leaves x unchanged
while(!x.isEmpty()) {
console.log(x.poll());
} // will print 0 1 3 4 5
x.trim(); // (optional) optimizes memory usage
*/
var defaultcomparator = function(a, b) {
return a < b
}
// the provided comparator function should take a, b and return *true* when a < b
export function FastPriorityQueue(comparator) {
if (!(this instanceof FastPriorityQueue)) return new FastPriorityQueue(comparator)
this.array = []
this.size = 0
this.compare = comparator || defaultcomparator
}
// copy the priority queue into another, and return it. Queue items are shallow-copied.
// Runs in `O(n)` time.
FastPriorityQueue.prototype.clone = function() {
var fpq = new FastPriorityQueue(this.compare)
fpq.size = this.size
for (var i = 0; i < this.size; i++) {
fpq.array.push(this.array[i])
}
return fpq
}
// Add an element into the queue
// runs in O(log n) time
FastPriorityQueue.prototype.add = function(myval) {
var i = this.size
this.array[this.size] = myval
this.size += 1
var p
var ap
while (i > 0) {
p = (i - 1) >> 1
ap = this.array[p]
if (!this.compare(myval, ap)) {
break
}
this.array[i] = ap
i = p
}
this.array[i] = myval
}
// replace the content of the heap by provided array and "heapify it"
FastPriorityQueue.prototype.heapify = function(arr) {
this.array = arr
this.size = arr.length
var i
for (i = this.size >> 1; i >= 0; i--) {
this._percolateDown(i)
}
}
// for internal use
FastPriorityQueue.prototype._percolateUp = function(i, force) {
var myval = this.array[i]
var p
var ap
while (i > 0) {
p = (i - 1) >> 1
ap = this.array[p]
// force will skip the compare
if (!force && !this.compare(myval, ap)) {
break
}
this.array[i] = ap
i = p
}
this.array[i] = myval
}
// for internal use
FastPriorityQueue.prototype._percolateDown = function(i) {
var size = this.size
var hsize = this.size >>> 1
var ai = this.array[i]
var l
var r
var bestc
while (i < hsize) {
l = (i << 1) + 1
r = l + 1
bestc = this.array[l]
if (r < size) {
if (this.compare(this.array[r], bestc)) {
l = r
bestc = this.array[r]
}
}
if (!this.compare(bestc, ai)) {
break
}
this.array[i] = bestc
i = l
}
this.array[i] = ai
}
// internal
// _removeAt(index) will remove the item at the given index from the queue,
// retaining balance. returns the removed item, or undefined if nothing is removed.
FastPriorityQueue.prototype._removeAt = function(index) {
if (index > this.size - 1 || index < 0) return undefined
// impl1:
//this.array.splice(index, 1);
//this.heapify(this.array);
// impl2:
this._percolateUp(index, true)
return this.poll()
}
// remove(myval) will remove an item matching the provided value from the
// queue, checked for equality by using the queue's comparator.
// return true if removed, false otherwise.
FastPriorityQueue.prototype.remove = function(myval) {
for (var i = 0; i < this.size; i++) {
if (!this.compare(this.array[i], myval) && !this.compare(myval, this.array[i])) {
// items match, comparator returns false both ways, remove item
this._removeAt(i)
return true
}
}
return false
}
// internal
// removes and returns items for which the callback returns true.
FastPriorityQueue.prototype._batchRemove = function(callback, limit) {
// initialize return array with max size of the limit or current queue size
var retArr = new Array(limit ? limit : this.size)
var count = 0
if (typeof callback === 'function' && this.size) {
var i = 0
while (i < this.size && count < retArr.length) {
if (callback(this.array[i])) {
retArr[count] = this._removeAt(i)
count++
// move up a level in the heap if we remove an item
i = i >> 1
} else {
i++
}
}
}
retArr.length = count
return retArr
}
// removeOne(callback) will execute the callback function for each item of the queue
// and will remove the first item for which the callback will return true.
// return the removed item, or undefined if nothing is removed.
FastPriorityQueue.prototype.removeOne = function(callback) {
var arr = this._batchRemove(callback, 1)
return arr.length > 0 ? arr[0] : undefined
}
// remove(callback[, limit]) will execute the callback function for each item of
// the queue and will remove each item for which the callback returns true, up to
// a max limit of removed items if specified or no limit if unspecified.
// return an array containing the removed items.
FastPriorityQueue.prototype.removeMany = function(callback, limit) {
return this._batchRemove(callback, limit)
}
// Look at the top of the queue (one of the smallest elements) without removing it
// executes in constant time
//
// Calling peek on an empty priority queue returns
// the "undefined" value.
// https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/undefined
//
FastPriorityQueue.prototype.peek = function() {
if (this.size == 0) return undefined
return this.array[0]
}
// remove the element on top of the heap (one of the smallest elements)
// runs in logarithmic time
//
// If the priority queue is empty, the function returns the
// "undefined" value.
// https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/undefined
//
// For long-running and large priority queues, or priority queues
// storing large objects, you may want to call the trim function
// at strategic times to recover allocated memory.
FastPriorityQueue.prototype.poll = function() {
if (this.size == 0) return undefined
var ans = this.array[0]
if (this.size > 1) {
this.array[0] = this.array[--this.size]
this._percolateDown(0)
} else {
this.size -= 1
}
return ans
}
// This function adds the provided value to the heap, while removing
// and returning one of the smallest elements (like poll). The size of the queue
// thus remains unchanged.
FastPriorityQueue.prototype.replaceTop = function(myval) {
if (this.size == 0) return undefined
var ans = this.array[0]
this.array[0] = myval
this._percolateDown(0)
return ans
}
// recover unused memory (for long-running priority queues)
FastPriorityQueue.prototype.trim = function() {
this.array = this.array.slice(0, this.size)
}
// Check whether the heap is empty
FastPriorityQueue.prototype.isEmpty = function() {
return this.size === 0
}
// iterate over the items in order, pass a callback that receives (item, index) as args.
// TODO once we transpile, uncomment
// if (Symbol && Symbol.iterator) {
// FastPriorityQueue.prototype[Symbol.iterator] = function*() {
// if (this.isEmpty()) return;
// var fpq = this.clone();
// while (!fpq.isEmpty()) {
// yield fpq.poll();
// }
// };
// }
FastPriorityQueue.prototype.forEach = function(callback) {
if (this.isEmpty() || typeof callback != 'function') return
var i = 0
var fpq = this.clone()
while (!fpq.isEmpty()) {
callback(fpq.poll(), i++)
}
}
// return the k 'smallest' elements of the queue
// runs in O(k log k) time
// this is the equivalent of repeatedly calling poll, but
// it has a better computational complexity, which can be
// important for large data sets.
FastPriorityQueue.prototype.kSmallest = function(k) {
if (this.size == 0) return []
var comparator = this.compare
var arr = this.array
var fpq = new FastPriorityQueue(function(a, b) {
return comparator(arr[a], arr[b])
})
k = Math.min(this.size, k)
var smallest = new Array(k)
var j = 0
fpq.add(0)
while (j < k) {
var small = fpq.poll()
smallest[j++] = this.array[small]
var l = (small << 1) + 1
var r = l + 1
if (l < this.size) fpq.add(l)
if (r < this.size) fpq.add(r)
}
return smallest
}