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

Efficient way to implement Priority Queue in Javascript?

提问by sova

Priority Queues have a priority value and data, for every entry.

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

Thus, when adding a new element to the queue, it bubbles up to the surface if it has a higher priority value than elements already in the collection.

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

When one calls pop, we get the data for the element with highest priority.

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

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

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

Does it make sense to have a new object called PriorityQueue, create two methods (push and pop) that take two params (data, priority)? That much makes sense to me as a coder, but I'm uncertain of which data structure to use in the underbelly that will allow manipulation of the ordering of elements. Or can we just store it all in an array and walk through the array every time to grab the element with max priority?

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

What's a good way to do this?

有什么好方法可以做到这一点？

回答by gyre

Below is what I believe to be a truly efficient version of a PriorityQueuewhich uses an array-based binary heap (where the root is at index 0, and the children of a node at index iare at indices 2i + 1and 2i + 2, respectively).

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

This implementation includes the classical priority queue methods like push, peek, pop, and size, as well as convenience methods isEmptyand replace(the latter being a more efficient substitute for a popfollowed immediately by a push). Values are stored not as [value, priority]pairs, but simply as values; this allows for automatic prioritization of types that can be natively compared using the >operator. A custom comparator function passed to the PriorityQueueconstructor can be used to emulate the behavior of pairwise semantics, however, as shown in the example below.

此实现包括经典的优先级队列方法，如push、peek、pop和size，以及便利方法isEmptyand replace（后者是 apop后紧跟a 的更有效替代品push）。值不是[value, priority]成对存储，而是简单地存储为values；这允许自动对可以使用>运算符进行本地比较的类型进行优先级排序。PriorityQueue但是，传递给构造函数的自定义比较器函数可用于模拟成对语义的行为，如下例所示。

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

回答by ashiato

You should use standard libraries like e.g. the Closure Library (goog.structs.PriorityQueue):

您应该使用标准库，例如 Closure Library ( goog.structs.PriorityQueue)：

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

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

By clicking at the source code, you will know it is actually linking to goog.structs.Heapwhich you can follow:

通过单击源代码，您将知道它实际上是goog.structs.Heap您可以关注的链接：

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

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

回答by Lucio Paiva

I was not satisfied with the efficiency of existing priority queue implementations, so I decided to make my own:

我对现有优先级队列实现的效率不满意，所以我决定自己做：

https://github.com/luciopaiva/heapify

https://github.com/luciopaiva/heapify

npm i heapify

This will run faster than any other publicly known implementation due to the use of typed arrays.

由于使用类型化数组，这将比任何其他公知的实现运行得更快。

Works on both client and server ends, code base with 100% test coverage, tiny library (~100 LoC). Also, the interface is really simple. Here's some code:

适用于客户端和服务器端，具有 100% 测试覆盖率的代码库，小型库（~100 LoC）。此外，界面非常简单。这是一些代码：

import Heapify from "heapify";

const queue = new Heapify();
queue.push(1, 10);  // insert item with key=1, priority=10
queue.push(2, 5);  // insert item with key=2, priority=5
queue.pop();  // 2
queue.peek();  // 1
queue.peekPriority();  // 10