Spaces:
Build error
Build error
File size: 4,091 Bytes
c211499 |
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 |
import * as _ from 'lodash-es';
export { PriorityQueue };
/**
* A min-priority queue data structure. This algorithm is derived from Cormen,
* et al., "Introduction to Algorithms". The basic idea of a min-priority
* queue is that you can efficiently (in O(1) time) get the smallest key in
* the queue. Adding and removing elements takes O(log n) time. A key can
* have its priority decreased in O(log n) time.
*/
class PriorityQueue {
constructor() {
this._arr = [];
this._keyIndices = {};
}
/**
* Returns the number of elements in the queue. Takes `O(1)` time.
*/
size() {
return this._arr.length;
}
/**
* Returns the keys that are in the queue. Takes `O(n)` time.
*/
keys() {
return this._arr.map(function (x) {
return x.key;
});
}
/**
* Returns `true` if **key** is in the queue and `false` if not.
*/
has(key) {
return _.has(this._keyIndices, key);
}
/**
* Returns the priority for **key**. If **key** is not present in the queue
* then this function returns `undefined`. Takes `O(1)` time.
*
* @param {Object} key
*/
priority(key) {
var index = this._keyIndices[key];
if (index !== undefined) {
return this._arr[index].priority;
}
}
/**
* Returns the key for the minimum element in this queue. If the queue is
* empty this function throws an Error. Takes `O(1)` time.
*/
min() {
if (this.size() === 0) {
throw new Error('Queue underflow');
}
return this._arr[0].key;
}
/**
* Inserts a new key into the priority queue. If the key already exists in
* the queue this function returns `false`; otherwise it will return `true`.
* Takes `O(n)` time.
*
* @param {Object} key the key to add
* @param {Number} priority the initial priority for the key
*/
add(key, priority) {
var keyIndices = this._keyIndices;
key = String(key);
if (!_.has(keyIndices, key)) {
var arr = this._arr;
var index = arr.length;
keyIndices[key] = index;
arr.push({ key: key, priority: priority });
this._decrease(index);
return true;
}
return false;
}
/**
* Removes and returns the smallest key in the queue. Takes `O(log n)` time.
*/
removeMin() {
this._swap(0, this._arr.length - 1);
var min = this._arr.pop();
delete this._keyIndices[min.key];
this._heapify(0);
return min.key;
}
/**
* Decreases the priority for **key** to **priority**. If the new priority is
* greater than the previous priority, this function will throw an Error.
*
* @param {Object} key the key for which to raise priority
* @param {Number} priority the new priority for the key
*/
decrease(key, priority) {
var index = this._keyIndices[key];
if (priority > this._arr[index].priority) {
throw new Error(
'New priority is greater than current priority. ' +
'Key: ' +
key +
' Old: ' +
this._arr[index].priority +
' New: ' +
priority
);
}
this._arr[index].priority = priority;
this._decrease(index);
}
_heapify(i) {
var arr = this._arr;
var l = 2 * i;
var r = l + 1;
var largest = i;
if (l < arr.length) {
largest = arr[l].priority < arr[largest].priority ? l : largest;
if (r < arr.length) {
largest = arr[r].priority < arr[largest].priority ? r : largest;
}
if (largest !== i) {
this._swap(i, largest);
this._heapify(largest);
}
}
}
_decrease(index) {
var arr = this._arr;
var priority = arr[index].priority;
var parent;
while (index !== 0) {
parent = index >> 1;
if (arr[parent].priority < priority) {
break;
}
this._swap(index, parent);
index = parent;
}
}
_swap(i, j) {
var arr = this._arr;
var keyIndices = this._keyIndices;
var origArrI = arr[i];
var origArrJ = arr[j];
arr[i] = origArrJ;
arr[j] = origArrI;
keyIndices[origArrJ.key] = i;
keyIndices[origArrI.key] = j;
}
}
|