在Java中实现优先级队列的有效方法? [英] Efficient way to implement Priority Queue in Javascript?

问题描述

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

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.

在Java中有效地实现这种优先级队列是什么?

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

拥有一个名为PriorityQueue的新对象，创建两个采用两个参数(数据，优先级)的方法(推送和弹出)，是否有意义?作为一名编码员，这对我来说很有意义，但是我不确定要在下腹部使用哪种数据结构来控制元素的顺序.还是我们可以将它们全部存储在一个数组中，然后每次遍历该数组以获取具有最高优先级的元素?

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?

执行此操作的好方法是什么?

What's a good way to do this?

推荐答案

下面是我认为的 PriorityQueue 的真正有效版本，该版本使用基于数组的二进制堆(其中的根在索引 0 处，节点的子节点在索引 i 处在索引 2i + 1 和 2i + 2 ).

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

此实现包括经典优先级队列方法，例如 push ， peek ， pop 和 size 以及便捷的方法 isEmpty 和 replace (后者是 pop 的更有效替代品，紧随其后的是 push ).值不是以 [value，priority] 对的形式存储，而是以 value s的形式存储；这样可以自动确定可以使用> 运算符进行本地比较的类型的优先级.传递给 PriorityQueue 构造函数的自定义比较器函数可用于模拟成对语义的行为，如下面的示例所示.

This implementation includes the classical priority queue methods like push, peek, pop, and size, as well as convenience methods isEmpty and replace (the latter being a more efficient substitute for a pop followed 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 PriorityQueue constructor can be used to emulate the behavior of pairwise semantics, however, as shown in the example below.

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

这篇关于在Java中实现优先级队列的有效方法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！