@@ -47,20 +47,28 @@ module.exports = class PriorityQueue { |
47 | 47 | const setPosition = this.#setPosition; |
48 | 48 | const heap = this.#heap; |
49 | 49 | const size = this.#size; |
| 50 | + const hsize = size >> 1; |
50 | 51 | const item = heap[pos]; |
51 | 52 |
|
52 | | - while (pos * 2 <= size) { |
53 | | - let childIndex = pos * 2 + 1; |
54 | | - if (childIndex > size || compare(heap[pos * 2], heap[childIndex]) < 0) |
55 | | - childIndex = pos * 2; |
56 | | - const child = heap[childIndex]; |
57 | | - if (compare(item, child) <= 0) |
58 | | - break; |
| 53 | + while (pos <= hsize) { |
| 54 | + let child = pos << 1; |
| 55 | + const nextChild = child + 1; |
| 56 | + let childItem = heap[child]; |
| 57 | + |
| 58 | + if (nextChild <= size && compare(heap[nextChild], childItem) < 0) { |
| 59 | + child = nextChild; |
| 60 | + childItem = heap[nextChild]; |
| 61 | + } |
| 62 | + |
| 63 | + if (compare(item, childItem) <= 0) break; |
| 64 | + |
59 | 65 | if (setPosition !== undefined) |
60 | | - setPosition(child, pos); |
61 | | - heap[pos] = child; |
62 | | - pos = childIndex; |
| 66 | + setPosition(childItem, pos); |
| 67 | + |
| 68 | + heap[pos] = childItem; |
| 69 | + pos = child; |
63 | 70 | } |
| 71 | + |
64 | 72 | heap[pos] = item; |
65 | 73 | if (setPosition !== undefined) |
66 | 74 | setPosition(item, pos); |
@@ -73,27 +81,30 @@ module.exports = class PriorityQueue { |
73 | 81 | const item = heap[pos]; |
74 | 82 |
|
75 | 83 | while (pos > 1) { |
76 | | - const parent = heap[pos / 2 | 0]; |
77 | | - if (compare(parent, item) <= 0) |
| 84 | + const parent = pos >> 1; |
| 85 | + const parentItem = heap[parent]; |
| 86 | + if (compare(parentItem, item) <= 0) |
78 | 87 | break; |
79 | | - heap[pos] = parent; |
| 88 | + heap[pos] = parentItem; |
80 | 89 | if (setPosition !== undefined) |
81 | | - setPosition(parent, pos); |
82 | | - pos = pos / 2 | 0; |
| 90 | + setPosition(parentItem, pos); |
| 91 | + pos = parent; |
83 | 92 | } |
| 93 | + |
84 | 94 | heap[pos] = item; |
85 | 95 | if (setPosition !== undefined) |
86 | 96 | setPosition(item, pos); |
87 | 97 | } |
88 | 98 |
|
89 | 99 | removeAt(pos) { |
90 | 100 | const heap = this.#heap; |
91 | | - const size = --this.#size; |
92 | | - heap[pos] = heap[size + 1]; |
93 | | - heap[size + 1] = undefined; |
| 101 | + let size = this.#size; |
| 102 | + heap[pos] = heap[size]; |
| 103 | + heap[size] = undefined; |
| 104 | + size = --this.#size; |
94 | 105 |
|
95 | 106 | if (size > 0 && pos <= size) { |
96 | | - if (pos > 1 && this.#compare(heap[pos / 2 | 0], heap[pos]) > 0) |
| 107 | + if (pos > 1 && this.#compare(heap[pos >> 1], heap[pos]) > 0) |
97 | 108 | this.percolateUp(pos); |
98 | 109 | else |
99 | 110 | this.percolateDown(pos); |
|