1'use strict'; 2 3const { 4 Array, 5} = primordials; 6 7// The PriorityQueue is a basic implementation of a binary heap that accepts 8// a custom sorting function via its constructor. This function is passed 9// the two nodes to compare, similar to the native Array#sort. Crucially 10// this enables priority queues that are based on a comparison of more than 11// just a single criteria. 12 13module.exports = class PriorityQueue { 14 #compare = (a, b) => a - b; 15 #heap = new Array(64); 16 #setPosition; 17 #size = 0; 18 19 constructor(comparator, setPosition) { 20 if (comparator !== undefined) 21 this.#compare = comparator; 22 if (setPosition !== undefined) 23 this.#setPosition = setPosition; 24 } 25 26 insert(value) { 27 const heap = this.#heap; 28 const pos = ++this.#size; 29 heap[pos] = value; 30 31 if (heap.length === pos) 32 heap.length *= 2; 33 34 this.percolateUp(pos); 35 } 36 37 peek() { 38 return this.#heap[1]; 39 } 40 41 percolateDown(pos) { 42 const compare = this.#compare; 43 const setPosition = this.#setPosition; 44 const heap = this.#heap; 45 const size = this.#size; 46 const item = heap[pos]; 47 48 while (pos * 2 <= size) { 49 let childIndex = pos * 2 + 1; 50 if (childIndex > size || compare(heap[pos * 2], heap[childIndex]) < 0) 51 childIndex = pos * 2; 52 const child = heap[childIndex]; 53 if (compare(item, child) <= 0) 54 break; 55 if (setPosition !== undefined) 56 setPosition(child, pos); 57 heap[pos] = child; 58 pos = childIndex; 59 } 60 heap[pos] = item; 61 if (setPosition !== undefined) 62 setPosition(item, pos); 63 } 64 65 percolateUp(pos) { 66 const heap = this.#heap; 67 const compare = this.#compare; 68 const setPosition = this.#setPosition; 69 const item = heap[pos]; 70 71 while (pos > 1) { 72 const parent = heap[pos / 2 | 0]; 73 if (compare(parent, item) <= 0) 74 break; 75 heap[pos] = parent; 76 if (setPosition !== undefined) 77 setPosition(parent, pos); 78 pos = pos / 2 | 0; 79 } 80 heap[pos] = item; 81 if (setPosition !== undefined) 82 setPosition(item, pos); 83 } 84 85 removeAt(pos) { 86 const heap = this.#heap; 87 const size = --this.#size; 88 heap[pos] = heap[size + 1]; 89 heap[size + 1] = undefined; 90 91 if (size > 0 && pos <= size) { 92 if (pos > 1 && this.#compare(heap[pos / 2 | 0], heap[pos]) > 0) 93 this.percolateUp(pos); 94 else 95 this.percolateDown(pos); 96 } 97 } 98 99 shift() { 100 const heap = this.#heap; 101 const value = heap[1]; 102 if (value === undefined) 103 return; 104 105 this.removeAt(1); 106 107 return value; 108 } 109}; 110