|
| 1 | +/** |
| 2 | + * BinaryHeap class represents a binary heap data structure that can be configured as a Min Heap or Max Heap. |
| 3 | + * |
| 4 | + * Binary heaps are binary trees that are filled level by level and from left to right inside each level. |
| 5 | + * They have the property that any parent node has a smaller (for Min Heap) or greater (for Max Heap) priority |
| 6 | + * than its children, ensuring that the root of the tree always holds the extremal value. |
| 7 | + */ |
| 8 | +classBinaryHeap{ |
| 9 | +/** |
| 10 | + * Creates a new BinaryHeap instance. |
| 11 | + *@constructor |
| 12 | + *@param {Function} comparatorFunction - The comparator function used to determine the order of elements (e.g., minHeapComparator or maxHeapComparator). |
| 13 | + */ |
| 14 | +constructor(comparatorFunction){ |
| 15 | +/** |
| 16 | + * The heap array that stores elements. |
| 17 | + *@member {Array} |
| 18 | + */ |
| 19 | +this.heap=[] |
| 20 | + |
| 21 | +/** |
| 22 | + * The comparator function used for ordering elements in the heap. |
| 23 | + *@member {Function} |
| 24 | + */ |
| 25 | +this.comparator=comparatorFunction |
| 26 | +} |
| 27 | + |
| 28 | +/** |
| 29 | + * Inserts a new value into the heap. |
| 30 | + *@param {*} value - The value to be inserted into the heap. |
| 31 | + */ |
| 32 | +insert(value){ |
| 33 | +this.heap.push(value) |
| 34 | +this.#bubbleUp(this.heap.length-1) |
| 35 | +} |
| 36 | + |
| 37 | +/** |
| 38 | + * Returns the number of elements in the heap. |
| 39 | + *@returns {number} - The number of elements in the heap. |
| 40 | + */ |
| 41 | +size(){ |
| 42 | +returnthis.heap.length |
| 43 | +} |
| 44 | + |
| 45 | +/** |
| 46 | + * Checks if the heap is empty. |
| 47 | + *@returns {boolean} - True if the heap is empty, false otherwise. |
| 48 | + */ |
| 49 | +empty(){ |
| 50 | +returnthis.size()===0 |
| 51 | +} |
| 52 | + |
| 53 | +/** |
| 54 | + * Bubbles up a value from the specified index to maintain the heap property. |
| 55 | + *@param {number} currIdx - The index of the value to be bubbled up. |
| 56 | + *@private |
| 57 | + */ |
| 58 | + #bubbleUp(currIdx){ |
| 59 | +letparentIdx=Math.floor((currIdx-1)/2) |
| 60 | + |
| 61 | +while( |
| 62 | +currIdx>0&& |
| 63 | +this.comparator(this.heap[currIdx],this.heap[parentIdx]) |
| 64 | +){ |
| 65 | +this.#swap(currIdx,parentIdx) |
| 66 | +currIdx=parentIdx |
| 67 | +parentIdx=Math.floor((currIdx-1)/2) |
| 68 | +} |
| 69 | +} |
| 70 | + |
| 71 | +/** |
| 72 | + * Sinks down a value from the specified index to maintain the heap property. |
| 73 | + *@param {number} currIdx - The index of the value to be sunk down. |
| 74 | + *@private |
| 75 | + */ |
| 76 | + #sinkDown(currIdx){ |
| 77 | +letchildOneIdx=currIdx*2+1 |
| 78 | + |
| 79 | +while(childOneIdx<this.size()){ |
| 80 | +constchildTwoIdx=childOneIdx+1<this.size() ?childOneIdx+1 :-1 |
| 81 | +constswapIdx= |
| 82 | +childTwoIdx!==-1&& |
| 83 | +this.comparator(this.heap[childTwoIdx],this.heap[childOneIdx]) |
| 84 | + ?childTwoIdx |
| 85 | + :childOneIdx |
| 86 | + |
| 87 | +if(this.comparator(this.heap[swapIdx],this.heap[currIdx])){ |
| 88 | +this.#swap(currIdx,swapIdx) |
| 89 | +currIdx=swapIdx |
| 90 | +childOneIdx=currIdx*2+1 |
| 91 | +}else{ |
| 92 | +return |
| 93 | +} |
| 94 | +} |
| 95 | +} |
| 96 | + |
| 97 | +/** |
| 98 | + * Retrieves the top element of the heap without removing it. |
| 99 | + *@returns {*} - The top element of the heap. |
| 100 | + */ |
| 101 | +peek(){ |
| 102 | +returnthis.heap[0] |
| 103 | +} |
| 104 | + |
| 105 | +/** |
| 106 | + * Removes and returns the top element of the heap. |
| 107 | + *@returns {*} - The top element of the heap. |
| 108 | + */ |
| 109 | +extractTop(){ |
| 110 | +consttop=this.peek() |
| 111 | +constlast=this.heap.pop() |
| 112 | + |
| 113 | +if(!this.empty()){ |
| 114 | +this.heap[0]=last |
| 115 | +this.#sinkDown(0) |
| 116 | +} |
| 117 | + |
| 118 | +returntop |
| 119 | +} |
| 120 | + |
| 121 | +/** |
| 122 | + * Swaps elements at two specified indices in the heap. |
| 123 | + *@param {number} index1 - The index of the first element to be swapped. |
| 124 | + *@param {number} index2 - The index of the second element to be swapped. |
| 125 | + *@private |
| 126 | + */ |
| 127 | + #swap(index1,index2){ |
| 128 | +;[this.heap[index1],this.heap[index2]]=[ |
| 129 | +this.heap[index2], |
| 130 | +this.heap[index1] |
| 131 | +] |
| 132 | +} |
| 133 | +} |
| 134 | + |
| 135 | +/** |
| 136 | + * Comparator function for creating a Min Heap. |
| 137 | + *@param {*} a - The first element to compare. |
| 138 | + *@param {*} b - The second element to compare. |
| 139 | + *@returns {boolean} - True if 'a' should have higher priority than 'b' in the Min Heap, false otherwise. |
| 140 | + */ |
| 141 | +constminHeapComparator=(a,b)=>a<b |
| 142 | + |
| 143 | +/** |
| 144 | + * Comparator function for creating a Max Heap. |
| 145 | + *@param {*} a - The first element to compare. |
| 146 | + *@param {*} b - The second element to compare. |
| 147 | + *@returns {boolean} - True if 'a' should have higher priority than 'b' in the Max Heap, false otherwise. |
| 148 | + */ |
| 149 | +constmaxHeapComparator=(a,b)=>a>b |
| 150 | + |
| 151 | +export{BinaryHeap,minHeapComparator,maxHeapComparator} |