在JavaScript中实现优先级队列的有效方法？

Question

优先级队列对每个条目都有一个优先级值和数据。

因此，当向队列中添加新元素时，如果该元素的优先级值高于集合中已有的元素，则该元素会浮上表面。

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

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

有一个名为PriorityQueue的新对象，创建两个方法（push和pop）来获取两个参数（数据、优先级），这有意义吗？作为一个编码器，这对我来说是有意义的，但是我不确定在底层使用哪种数据结构来允许对元素的排序进行操作。或者我们可以仅仅将它全部存储在一个数组中，每次遍历数组来抓取具有最大优先级的元素吗？

这样做有什么好方法？

Answer 1

您应该使用标准库，例如闭包库(goog.structs.priorityqueue):

https://google.github.io/closure-library/api/goog.structs.priorityqueue.html

通过单击源代码，您将知道它实际上链接到goog.structs.heap，您可以遵循以下内容：

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

Answer 2

下面是我认为真正有效的priorityqueue版本，它使用基于数组的二进制堆（其中根位于index0，indexI处的节点的子级分别位于index2I+1和2I+2处）。

此实现包括典型的优先级队列方法，如push、peek、pop和size以及方便方法isempty和replace（后者是pop的更有效的替代品，后接push)。值不是作为[value,priority]对存储的，而是作为value存储的；这允许对可以使用运算符进行本机比较的类型进行自动优先排序。但是，可以使用传递给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;
    }
  }
}

null

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