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


优先级队列具有每个条目的优先级值和数据。

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

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

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

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

这样做的好方法是什么？


5767
2018-03-21 06:00


起源

答案:

以下是我认为真正有效的版本 PriorityQueue 它使用基于数组的二进制堆（其中根位于索引处） 0，以及索引处节点的子节点 i 在指数 2i + 1 和 2i + 2， 分别）。

此实现包括经典的优先级队列方法 push， peek， pop，和 size，以及方便的方法 isEmpty 和 replace （后者是一种更有效的替代品 pop 紧接着就是一个 push）。值存储不是 [value, priority] 对，但简单地说 valueS;这允许自动确定可以使用本机比较的类型的优先级 > 运营商。自定义比较器函数传递给 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'
}
.as-console-wrapper{min-height:100%}


11
2018-03-21 06:20


很酷，非常感谢！我想知道：在实现中使用2个独立的数组更有意义（一个用于数据，一个用于优先级，只是数据[i]和优先级[i]是相同的“对”）或使用2d [] []数组？因为，第一个选项仅使用2n空间，但第二个选项最多可使用n ^ 2 - sova
我只想使用一个数组。两种选择都使用 2n space，因为多维数组中的每一行只有两个元素（固定长度）。 - gyre
啊哈，我明白了！再次感谢朋友，非常有帮助。 - sova
@vaxquis我知道这已经很久了，但我想我会告诉你我更新了我的答案，以提高它的时间复杂度。虽然我现在并没有花太多时间在SO上，但随着我对数据结构的了解越来越多，这个答案也让我感到烦恼，我终于抽出一些时间来解决它。 （我会删除它，但它被接受了。）如果你有任何进一步的建议，请告诉我......这次我会尝试更加迅速。 - gyre
@gyre很高兴见到你的进步; IMVHO现在你的答案好多了。仍然，我想分享两个挑剔：1。分裂声明，如 if (bottom > top) this._swap(top, bottom); 分为两行（还有1TBS，我强烈建议在教程代码中使用它，但这又是另一个野兽），2。使用临时变量来存储必须重复计算的值（特别 如果它们是循环中使用的函数调用的结果，例如，你的 left(node)， right(node)， this.size() 等等......那还是 真 在JS / ES代码中有所作为。 - vaxquis

答案:

以下是我认为真正有效的版本 PriorityQueue 它使用基于数组的二进制堆（其中根位于索引处） 0，以及索引处节点的子节点 i 在指数 2i + 1 和 2i + 2， 分别）。

此实现包括经典的优先级队列方法 push， peek， pop，和 size，以及方便的方法 isEmpty 和 replace （后者是一种更有效的替代品 pop 紧接着就是一个 push）。值存储不是 [value, priority] 对，但简单地说 valueS;这允许自动确定可以使用本机比较的类型的优先级 > 运营商。自定义比较器函数传递给 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'
}
.as-console-wrapper{min-height:100%}


11
2018-03-21 06:20


很酷，非常感谢！我想知道：在实现中使用2个独立的数组更有意义（一个用于数据，一个用于优先级，只是数据[i]和优先级[i]是相同的“对”）或使用2d [] []数组？因为，第一个选项仅使用2n空间，但第二个选项最多可使用n ^ 2 - sova
我只想使用一个数组。两种选择都使用 2n space，因为多维数组中的每一行只有两个元素（固定长度）。 - gyre
啊哈，我明白了！再次感谢朋友，非常有帮助。 - sova
@vaxquis我知道这已经很久了，但我想我会告诉你我更新了我的答案，以提高它的时间复杂度。虽然我现在并没有花太多时间在SO上，但随着我对数据结构的了解越来越多，这个答案也让我感到烦恼，我终于抽出一些时间来解决它。 （我会删除它，但它被接受了。）如果你有任何进一步的建议，请告诉我......这次我会尝试更加迅速。 - gyre
@gyre很高兴见到你的进步; IMVHO现在你的答案好多了。仍然，我想分享两个挑剔：1。分裂声明，如 if (bottom > top) this._swap(top, bottom); 分为两行（还有1TBS，我强烈建议在教程代码中使用它，但这又是另一个野兽），2。使用临时变量来存储必须重复计算的值（特别 如果它们是循环中使用的函数调用的结果，例如，你的 left(node)， right(node)， this.size() 等等......那还是 真 在JS / ES代码中有所作为。 - vaxquis

您应该使用标准库，例如关闭图书馆（goog.structs.PriorityQueue）：

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

通过单击源代码，您将知道它实际上是链接到 goog.structs.Heap 你可以遵循：

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


4
2017-08-21 07:17



热门问题

不使用eval / new函数的JavaScript模板库 当涉及内部类时，Java继承如何工作 .NET Windows服务的奇怪问题 在.ipa或.app下查找App ID 快速入门XSLT参考[关闭] 如何找出Android应用程序中未使用的资源 Ruby中并发的同步方法[重复] 将std :: chrono :: system_clock :: time_point转换为struct timeval并返回 Google Drive API V3（javascript）更新文件内容 Bootstrap 3.0 - 将元素推到底部 受密码保护的.NET ClickOnce部署？ 如何用postgresql安装wordpress coq Set或Type如何成为命题 硒滚动元素进入（中心）视图 在Spring Transaction JUnit测试中自动装配Hibernate会话的正确方法 Git的Dockerfile策略 如何在FOS_PICKFOLDER中使用IFileDialog，同时仍在对话框中显示文件名 在Firefox扩展中复制Google Chrome浏览器操作弹出效果 CakePHP找到MAX 芹菜 - 完成任务的召唤功能 从使用fmemopen创建的流中读取宽字符 .NET是否为每个程序集创建一个字符串实习池？ DefaultModelBinder不绑定嵌套模型 Navigator.MediaDevices.getUserMedia（）使用了哪些相机通信标准？ 选择命名空间名称时应该知道什么？ cout Swagger Codegen CLI Java客户端 - 如何正确使用它 一个很好的哈希函数用于采访整数，字符串？ Maven 3 ciManagement配置的目的是什么？ 如何通过语言文化获取代码页？
licensed under cc by-sa 3.0 with attribution.
隐私政策 往来