lib: optimize priority queue · nodejs/node@cea50b7

const setPosition = this.#setPosition;

const heap = this.#heap;

const size = this.#size;

const hsize = size >> 1;

const item = heap[pos];

while (pos * 2 <= size) {

let childIndex = pos * 2 + 1;

if (childIndex > size || compare(heap[pos * 2], heap[childIndex]) < 0)

childIndex = pos * 2;

const child = heap[childIndex];

if (compare(item, child) <= 0)

break;

while (pos <= hsize) {

let child = pos << 1;

const nextChild = child + 1;

let childItem = heap[child];

if (nextChild <= size && compare(heap[nextChild], childItem) < 0) {

child = nextChild;

childItem = heap[nextChild];

}

if (compare(item, childItem) <= 0) break;

if (setPosition !== undefined)

setPosition(child, pos);

heap[pos] = child;

pos = childIndex;

setPosition(childItem, pos);

heap[pos] = childItem;

pos = child;

}

heap[pos] = item;

if (setPosition !== undefined)

setPosition(item, pos);

const item = heap[pos];

while (pos > 1) {

const parent = heap[pos / 2 | 0];

if (compare(parent, item) <= 0)

const parent = pos >> 1;

const parentItem = heap[parent];

if (compare(parentItem, item) <= 0)

break;

heap[pos] = parent;

heap[pos] = parentItem;

if (setPosition !== undefined)

setPosition(parent, pos);

pos = pos / 2 | 0;

setPosition(parentItem, pos);

pos = parent;

}

heap[pos] = item;

if (setPosition !== undefined)

setPosition(item, pos);

}

removeAt(pos) {

const heap = this.#heap;

const size = --this.#size;

heap[pos] = heap[size + 1];

heap[size + 1] = undefined;

let size = this.#size;

heap[pos] = heap[size];

heap[size] = undefined;

size = --this.#size;

if (size > 0 && pos <= size) {

if (pos > 1 && this.#compare(heap[pos / 2 | 0], heap[pos]) > 0)

if (pos > 1 && this.#compare(heap[pos >> 1], heap[pos]) > 0)

this.percolateUp(pos);

else

this.percolateDown(pos);