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