Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 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 | 10x 10x 10x 10x 10x 10x 1x 54838x 12342x 2x 40x 39x 39x 1x 1x 5x 1x 1x 39x 4788x 4788x 4788x 1x 36x 36x 1x 15610x 15610x 15610x 15610x 15610x 15610x 15610x 17602x 17602x 17602x 1885x 15717x 17602x 904x 17602x 1992x 1992x 15610x 1x 12042x 12042x 13304x 1x 2786x 2786x 2786x 2786x 2786x 2786x 2210x 576x 2786x 2583x 2583x 490x 490x 2093x 2786x 212x 212x 2786x 1x 2306x 2306x 2306x 2306x 2306x 2306x 2306x 2306x 2306x | import Check from "./Check.js";
import defined from "./defined.js";
/**
* Array implementation of a heap.
*
* @alias Heap
* @constructor
* @private
*
* @param {object} options Object with the following properties:
* @param {Heap.ComparatorCallback} options.comparator The comparator to use for the heap. If comparator(a, b) is less than 0, sort a to a lower index than b, otherwise sort to a higher index.
*/
function Heap(options) {
//>>includeStart('debug', pragmas.debug);
Check.typeOf.object("options", options);
Check.defined("options.comparator", options.comparator);
//>>includeEnd('debug');
this._comparator = options.comparator;
this._array = [];
this._length = 0;
this._maximumLength = undefined;
}
Object.defineProperties(Heap.prototype, {
/**
* Gets the length of the heap.
*
* @memberof Heap.prototype
*
* @type {number}
* @readonly
*/
length: {
get: function () {
return this._length;
},
},
/**
* Gets the internal array.
*
* @memberof Heap.prototype
*
* @type {Array}
* @readonly
*/
internalArray: {
get: function () {
return this._array;
},
},
/**
* Gets and sets the maximum length of the heap.
*
* @memberof Heap.prototype
*
* @type {number}
*/
maximumLength: {
get: function () {
return this._maximumLength;
},
set: function (value) {
//>>includeStart('debug', pragmas.debug);
Check.typeOf.number.greaterThanOrEquals("maximumLength", value, 0);
//>>includeEnd('debug');
const originalLength = this._length;
if (value < originalLength) {
const array = this._array;
// Remove trailing references
for (let i = value; i < originalLength; ++i) {
array[i] = undefined;
}
this._length = value;
array.length = value;
}
this._maximumLength = value;
},
},
/**
* The comparator to use for the heap. If comparator(a, b) is less than 0, sort a to a lower index than b, otherwise sort to a higher index.
*
* @memberof Heap.prototype
*
* @type {Heap.ComparatorCallback}
*/
comparator: {
get: function () {
return this._comparator;
},
},
});
function swap(array, a, b) {
const temp = array[a];
array[a] = array[b];
array[b] = temp;
}
/**
* Resizes the internal array of the heap.
*
* @param {number} [length] The length to resize internal array to. Defaults to the current length of the heap.
*/
Heap.prototype.reserve = function (length) {
length = length ?? this._length;
this._array.length = length;
};
/**
* Update the heap so that index and all descendants satisfy the heap property.
*
* @param {number} [index=0] The starting index to heapify from.
*/
Heap.prototype.heapify = function (index) {
index = index ?? 0;
const length = this._length;
const comparator = this._comparator;
const array = this._array;
let candidate = -1;
let inserting = true;
while (inserting) {
const right = 2 * (index + 1);
const left = right - 1;
if (left < length && comparator(array[left], array[index]) < 0) {
candidate = left;
} else {
candidate = index;
}
if (right < length && comparator(array[right], array[candidate]) < 0) {
candidate = right;
}
if (candidate !== index) {
swap(array, candidate, index);
index = candidate;
} else {
inserting = false;
}
}
};
/**
* Resort the heap.
*/
Heap.prototype.resort = function () {
const length = this._length;
for (let i = Math.ceil(length / 2); i >= 0; --i) {
this.heapify(i);
}
};
/**
* Insert an element into the heap. If the length would grow greater than maximumLength
* of the heap, extra elements are removed.
*
* @param {*} element The element to insert
*
* @return {*} The element that was removed from the heap if the heap is at full capacity.
*/
Heap.prototype.insert = function (element) {
//>>includeStart('debug', pragmas.debug);
Check.defined("element", element);
//>>includeEnd('debug');
const array = this._array;
const comparator = this._comparator;
const maximumLength = this._maximumLength;
let index = this._length++;
if (index < array.length) {
array[index] = element;
} else {
array.push(element);
}
while (index !== 0) {
const parent = Math.floor((index - 1) / 2);
if (comparator(array[index], array[parent]) < 0) {
swap(array, index, parent);
index = parent;
} else {
break;
}
}
let removedElement;
if (defined(maximumLength) && this._length > maximumLength) {
removedElement = array[maximumLength];
this._length = maximumLength;
}
return removedElement;
};
/**
* Remove the element specified by index from the heap and return it.
*
* @param {number} [index=0] The index to remove.
* @returns {*} The specified element of the heap.
*/
Heap.prototype.pop = function (index) {
index = index ?? 0;
Iif (this._length === 0) {
return undefined;
}
//>>includeStart('debug', pragmas.debug);
Check.typeOf.number.lessThan("index", index, this._length);
//>>includeEnd('debug');
const array = this._array;
const root = array[index];
swap(array, index, --this._length);
this.heapify(index);
array[this._length] = undefined; // Remove trailing reference
return root;
};
/**
* The comparator to use for the heap.
* @callback Heap.ComparatorCallback
* @param {*} a An element in the heap.
* @param {*} b An element in the heap.
* @returns {number} If the result of the comparison is less than 0, sort a to a lower index than b, otherwise sort to a higher index.
*/
export default Heap;
|