Efficient way to implement priority queue in Javascript?

Question

Priority queues have a priority value and data for each record.

Thus, when a new item is added to the queue, it pops up to the surface if it has a higher priority value than items that are already in the collection.

When you call pop, we get the data for the item with the highest priority.

What is the efficient implementation of such a priority queue in Javascript?

Does it make sense to have a new PriorityQueue object, create two methods (push and pop) that take two parameters (data, priority)? For me it makes sense as an encoder, but I'm not sure which data structure to use in the underbelly, which will allow me to manipulate the ordering of the elements. Or can we just store all this in an array and go through the array each time to capture the element with the highest priority?

What a good way to do this?

Answer 1

Below, I believe that this is a really efficient version of PriorityQueue that uses an array-based binary heap (where the root is at index 0 ) and the node's children at index i have indices 2i + 1 and 2i + 2 respectively).

This implementation includes classic priority queue methods such as push , peek , pop and size , as well as convenient isEmpty and replace methods (the latter is a more efficient replacement for a pop , followed immediately by a push ). Values ​​are not stored as [value, priority] pairs, but simply as value s; this allows you to automatically prioritize types that can be compared with the source code using the > operator. The custom comparator function passed to the PriorityQueue constructor can be used to emulate the behavior of paired semantics, however, as shown in the example below.

Heap based implementation :

 const top = 0; const parent = i => ((i + 1) >>> 1) - 1; const left = i => (i << 1) + 1; const right = i => (i + 1) << 1; class PriorityQueue { constructor(comparator = (a, b) => a > b) { this._heap = []; this._comparator = comparator; } size() { return this._heap.length; } isEmpty() { return this.size() == 0; } peek() { return this._heap[top]; } push(...values) { values.forEach(value => { this._heap.push(value); this._siftUp(); }); return this.size(); } pop() { const poppedValue = this.peek(); const bottom = this.size() - 1; if (bottom > top) { this._swap(top, bottom); } this._heap.pop(); this._siftDown(); return poppedValue; } replace(value) { const replacedValue = this.peek(); this._heap[top] = value; this._siftDown(); return replacedValue; } _greater(i, j) { return this._comparator(this._heap[i], this._heap[j]); } _swap(i, j) { [this._heap[i], this._heap[j]] = [this._heap[j], this._heap[i]]; } _siftUp() { let node = this.size() - 1; while (node > top && this._greater(node, parent(node))) { this._swap(node, parent(node)); node = parent(node); } } _siftDown() { let node = top; while ( (left(node) < this.size() && this._greater(left(node), node)) || (right(node) < this.size() && this._greater(right(node), node)) ) { let maxChild = (right(node) < this.size() && this._greater(right(node), left(node))) ? right(node) : left(node); this._swap(node, maxChild); node = maxChild; } } } 

---

Example:

 {const top=0,parent=c=>(c+1>>>1)-1,left=c=>(c<<1)+1,right=c=>c+1<<1;class PriorityQueue{constructor(c=(d,e)=>d>e){this._heap=[],this._comparator=c}size(){return this._heap.length}isEmpty(){return 0==this.size()}peek(){return this._heap[top]}push(...c){return c.forEach(d=>{this._heap.push(d),this._siftUp()}),this.size()}pop(){const c=this.peek(),d=this.size()-1;return d>top&&this._swap(top,d),this._heap.pop(),this._siftDown(),c}replace(c){const d=this.peek();return this._heap[top]=c,this._siftDown(),d}_greater(c,d){return this._comparator(this._heap[c],this._heap[d])}_swap(c,d){[this._heap[c],this._heap[d]]=[this._heap[d],this._heap[c]]}_siftUp(){for(let c=this.size()-1;c>top&&this._greater(c,parent(c));)this._swap(c,parent(c)),c=parent(c)}_siftDown(){for(let d,c=top;left(c)<this.size()&&this._greater(left(c),c)||right(c)<this.size()&&this._greater(right(c),c);)d=right(c)<this.size()&&this._greater(right(c),left(c))?right(c):left(c),this._swap(c,d),c=d}}window.PriorityQueue=PriorityQueue} // Default comparison semantics const queue = new PriorityQueue(); queue.push(10, 20, 30, 40, 50); console.log('Top:', queue.peek()); //=> 50 console.log('Size:', queue.size()); //=> 5 console.log('Contents:'); while (!queue.isEmpty()) { console.log(queue.pop()); //=> 40, 30, 20, 10 } // Pairwise comparison semantics const pairwiseQueue = new PriorityQueue((a, b) => a[1] > b[1]); pairwiseQueue.push(['low', 0], ['medium', 5], ['high', 10]); console.log('\nContents:'); while (!pairwiseQueue.isEmpty()) { console.log(pairwiseQueue.pop()[0]); //=> 'high', 'medium', 'low' } 

 .as-console-wrapper{min-height:100%} 

Answer 2

You should use standard libraries, for example, for example. Closing library ( goog.structs.PriorityQueue ):

https://google.imtqy.com/closure-library/api/goog.structs.PriorityQueue.html

By clicking on the source code, you will find out that it actually refers to goog.structs.Heap , which you can use:

https://github.com/google/closure-library/blob/master/closure/goog/structs/heap.js