对于每个条目，优先级队列都有一个优先级值和数据。在Javascript中实现优先队列的有效方法？

因此，当向队列中添加一个新元素时，如果它具有比集合中已有的元素更高的优先级值，则它会冒泡到表面。

当我们调用pop时，我们得到最高优先级元素的数据。

什么是在Javascript中的这种优先级队列的有效实现？

是否有意义有一个名为PriorityQueue的新对象，创建两个方法（push和pop），其中包含两个参数（数据，优先级）？对我来说，作为一个编码器是很有意义的，但是我不确定在哪个数据结构中使用的下腹部将允许操纵元素的排序。或者我们可以将它全部存储在一个数组中，并且每次遍历数组以获取最大优先级的元素？

这样做的好方法是什么？

来源

2017-03-21 sova

下面是我认为是它使用基于阵列的二元堆（其中的根源是在指数0一个PriorityQueue的真正有效的版本和节点的索引i孩子都处于指数2i + 1和2i + 2 ，分别）。

该实施方式包括经典的优先级队列的方法，如push，peek，pop，并size，以及方便的方法isEmpty和replace（后者是用于pop的更有效的替代紧跟一个push）。数值不是以[value, priority]对存储，而是简单地存储为value s;这允许使用>运算符自动比较类型的自动优先级。传递给PriorityQueue构造函数的自定义比较函数可用于模拟成对语义的行为，但是，如下例所示。

基于堆的实施：

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; 
    } 
    } 
}

实施例：

{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' 
 
}