Commit 56abc4a
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -1,9 +1,5 @@ | |||
| 1 | 1 | 'use strict'; | |
| 2 | 2 | ||
| 3 | - const { | ||
| 4 | - Array, | ||
| 5 | - } = primordials; | ||
| 6 | - | ||
| 7 | 3 | // The PriorityQueue is a basic implementation of a binary heap that accepts | |
| 8 | 4 | // a custom sorting function via its constructor. This function is passed | |
| 9 | 5 | // the two nodes to compare, similar to the native Array#sort. Crucially | |
@@ -12,7 +8,7 @@ const { | |||
| 12 | 8 | ||
| 13 | 9 | module.exports = class PriorityQueue { | |
| 14 | 10 | #compare = (a, b) => a - b; | |
| 15 | - #heap = new Array(64); | ||
| 11 | + #heap = [undefined, undefined]; | ||
| 16 | 12 | #setPosition; | |
| 17 | 13 | #size = 0; | |
| 18 | 14 | ||
@@ -28,9 +24,6 @@ module.exports = class PriorityQueue { | |||
| 28 | 24 | const pos = ++this.#size; | |
| 29 | 25 | heap[pos] = value; | |
| 30 | 26 | ||
| 31 | - if (heap.length === pos) | ||
| 32 | - heap.length *= 2; | ||
| 33 | - | ||
| 34 | 27 | this.percolateUp(pos); | |
| 35 | 28 | } | |
| 36 | 29 | ||
@@ -45,6 +38,7 @@ module.exports = class PriorityQueue { | |||
| 45 | 38 | percolateDown(pos) { | |
| 46 | 39 | const compare = this.#compare; | |
| 47 | 40 | const setPosition = this.#setPosition; | |
| 41 | + const hasSetPosition = setPosition !== undefined; | ||
| 48 | 42 | const heap = this.#heap; | |
| 49 | 43 | const size = this.#size; | |
| 50 | 44 | const hsize = size >> 1; | |
@@ -62,22 +56,23 @@ module.exports = class PriorityQueue { | |||
| 62 | 56 | ||
| 63 | 57 | if (compare(item, childItem) <= 0) break; | |
| 64 | 58 | ||
| 65 | - if (setPosition !== undefined) | ||
| 59 | + if (hasSetPosition) | ||
| 66 | 60 | setPosition(childItem, pos); | |
| 67 | 61 | ||
| 68 | 62 | heap[pos] = childItem; | |
| 69 | 63 | pos = child; | |
| 70 | 64 | } | |
| 71 | 65 | ||
| 72 | 66 | heap[pos] = item; | |
| 73 | - if (setPosition !== undefined) | ||
| 67 | + if (hasSetPosition) | ||
| 74 | 68 | setPosition(item, pos); | |
| 75 | 69 | } | |
| 76 | 70 | ||
| 77 | 71 | percolateUp(pos) { | |
| 78 | 72 | const heap = this.#heap; | |
| 79 | 73 | const compare = this.#compare; | |
| 80 | 74 | const setPosition = this.#setPosition; | |
| 75 | + const hasSetPosition = setPosition !== undefined; | ||
| 81 | 76 | const item = heap[pos]; | |
| 82 | 77 | ||
| 83 | 78 | while (pos > 1) { | |
@@ -86,13 +81,13 @@ module.exports = class PriorityQueue { | |||
| 86 | 81 | if (compare(parentItem, item) <= 0) | |
| 87 | 82 | break; | |
| 88 | 83 | heap[pos] = parentItem; | |
| 89 | - if (setPosition !== undefined) | ||
| 84 | + if (hasSetPosition) | ||
| 90 | 85 | setPosition(parentItem, pos); | |
| 91 | 86 | pos = parent; | |
| 92 | 87 | } | |
| 93 | 88 | ||
| 94 | 89 | heap[pos] = item; | |
| 95 | - if (setPosition !== undefined) | ||
| 90 | + if (hasSetPosition) | ||
| 96 | 91 | setPosition(item, pos); | |
| 97 | 92 | } | |
| 98 | 93 | ||
0 commit comments