优先队列为每个条目设置了优先级值和数据。
因此，当向队列添加新元素时，如果其优先级值比集合中已有的元素高，则会冒泡到表面。
调用pop时，我们将获取具有最高优先级的元素的数据。
在Javascript中，实现这样一个优先队列的有效方法是什么？
是否有必要创建一个名为PriorityQueue的新对象，并创建两个方法（push和pop），它们接受两个参数（数据、优先级）？对我来说作为一个编码人员，这已经很清楚了，但我不确定在底层使用哪种数据结构可以允许元素排序操作。或者我们可以把它全部存储在数组中，并且每次遍历数组来获取具有最大优先级的元素。那么，怎么做才是好的？
以下是我认为是真正高效的 PriorityQueue 版本，它使用基于数组的二叉堆（根节点在索引 0，节点的子节点在索引 2i + 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;
}
}
}
{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%}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.jshttps://github.com/luciopaiva/heapify
npm i heapify
由于使用了类型化数组，这将比任何其他公开已知的实现运行得更快。
适用于客户端和服务器端，代码基础覆盖率达到100％，库体积小（约100行代码）。而且，接口非常简单。以下是一些代码：
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
我在这里提供我使用的实现方式。我做出了以下决策：
<，>，...）进行值的比较。这对数字、大整数、字符串和日期实例都有效。如果值是无法以这种方式很好地排序的对象，则应覆盖其 valueOf 以保证所需的顺序。或者，应将这些对象作为有效负载提供，并将真正定义顺序的对象属性作为值（在第一个数组位置）。heapq 模块的工作方式，并给人一种“轻量级”的感觉：您直接使用自己的数组进行操作。没有 new，没有继承，只是在数组上执行普通函数。下面是这些函数的集合，包括注释和简单的演示：
/* MinHeap:
* A collection of functions that operate on an array
* of [key,...data] elements (nodes).
*/
const MinHeap = {
/* siftDown:
* The node at the given index of the given heap is sifted down in
* its subtree until it does not have a child with a lesser value.
*/
siftDown(arr, i=0, value=arr[i]) {
if (i < arr.length) {
let key = value[0]; // Grab the value to compare with
while (true) {
// Choose the child with the least value
let j = i*2+1;
if (j+1 < arr.length && arr[j][0] > arr[j+1][0]) j++;
// If no child has lesser value, then we've found the spot!
if (j >= arr.length || key <= arr[j][0]) break;
// Copy the selected child node one level up...
arr[i] = arr[j];
// ...and consider the child slot for putting our sifted node
i = j;
}
arr[i] = value; // Place the sifted node at the found spot
}
},
/* heapify:
* The given array is reordered in-place so that it becomes a valid heap.
* Elements in the given array must have a [0] property (e.g. arrays).
* That [0] value serves as the key to establish the heap order. The rest
* of such an element is just payload. It also returns the heap.
*/
heapify(arr) {
// Establish heap with an incremental, bottom-up process
for (let i = arr.length>>1; i--; ) this.siftDown(arr, i);
return arr;
},
/* pop:
* Extracts the root of the given heap, and returns it (the subarray).
* Returns undefined if the heap is empty
*/
pop(arr) {
// Pop the last leaf from the given heap, and exchange it with its root
return this.exchange(arr, arr.pop()); // Returns the old root
},
/* exchange:
* Replaces the root node of the given heap with the given node, and
* returns the previous root. Returns the given node if the heap is empty.
* This is similar to a call of pop and push, but is more efficient.
*/
exchange(arr, value) {
if (!arr.length) return value;
// Get the root node, so to return it later
let oldValue = arr[0];
// Inject the replacing node using the sift-down process
this.siftDown(arr, 0, value);
return oldValue;
},
/* push:
* Inserts the given node into the given heap. It returns the heap.
*/
push(arr, value) {
let key = value[0],
// First assume the insertion spot is at the very end (as a leaf)
i = arr.length,
j;
// Then follow the path to the root, moving values down for as long
// as they are greater than the value to be inserted
while ((j = (i-1)>>1) >= 0 && key < arr[j][0]) {
arr[i] = arr[j];
i = j;
}
// Found the insertion spot
arr[i] = value;
return arr;
}
};
// Simple Demo:
let heap = [];
MinHeap.push(heap, [26, "Helen"]);
MinHeap.push(heap, [15, "Mike"]);
MinHeap.push(heap, [20, "Samantha"]);
MinHeap.push(heap, [21, "Timothy"]);
MinHeap.push(heap, [19, "Patricia"]);
let [age, name] = MinHeap.pop(heap);
console.log(`${name} is the youngest with ${age} years`);
([age, name] = MinHeap.pop(heap));
console.log(`Next is ${name} with ${age} years`);为了举一个更加贴近实际的例子，可以参考Dijkstra最短路径算法的实现。
这里有一个相同的MinHeap集合，但是被压缩了，并且还有它的镜像MaxHeap：
const MinHeap={siftDown(h,i=0,v=h[i]){if(i<h.length){let k=v[0];while(1){let j=i*2+1;if(j+1<h.length&&h[j][0]>h[j+1][0])j++;if(j>=h.length||k<=h[j][0])break;h[i]=h[j];i=j;}h[i]=v}},heapify(h){for(let i=h.length>>1;i--;)this.siftDown(h,i);return h},pop(h){return this.exchange(h,h.pop())},exchange(h,v){if(!h.length)return v;let w=h[0];this.siftDown(h,0,v);return w},push(h,v){let k=v[0],i=h.length,j;while((j=(i-1)>>1)>=0&&k<h[j][0]){h[i]=h[j];i=j}h[i]=v;return h}};
const MaxHeap={siftDown(h,i=0,v=h[i]){if(i<h.length){let k=v[0];while(1){let j=i*2+1;if(j+1<h.length&&h[j][0]<h[j+1][0])j++;if(j>=h.length||k>=h[j][0])break;h[i]=h[j];i=j;}h[i]=v}},heapify(h){for(let i=h.length>>1;i--;)this.siftDown(h,i);return h},pop(h){return this.exchange(h,h.pop())},exchange(h,v){if(!h.length)return v;let w=h[0];this.siftDown(h,0,v);return w},push(h,v){let k=v[0],i=h.length,j;while((j=(i-1)>>1)>=0&&k>h[j][0]){h[i]=h[j];i=j}h[i]=v;return h}};
heap = MinHeap(); heap.push(prio, value)等等。 - wihlke我从@gyre的回答中得到了一些灵感，并用TypeScript写了一个极简版本，压缩后大约只有550字节。
type Comparator<T> = (valueA: T, valueB: T) => number;
const swap = (arr: unknown[], i: number, j: number) => {
[arr[i], arr[j]] = [arr[j], arr[i]];
};
class PriorityQueue<T> {
#heap;
#isGreater;
constructor(comparator: Comparator<T>);
constructor(comparator: Comparator<T>, init: T[] = []) {
this.#heap = init;
this.#isGreater = (a: number, b: number) =>
comparator(init[a] as T, init[b] as T) > 0;
}
get size(): number {
return this.#heap.length;
}
peek(): T | undefined {
return this.#heap[0];
}
add(value: T): void {
this.#heap.push(value);
this.#siftUp();
}
poll(): T | undefined;
poll(
heap = this.#heap,
value = heap[0],
length = heap.length
): T | undefined {
if (length) {
swap(heap, 0, length - 1);
}
heap.pop();
this.#siftDown();
return value;
}
#siftUp(): void;
#siftUp(node = this.size - 1, parent = ((node + 1) >>> 1) - 1): void {
for (
;
node && this.#isGreater(node, parent);
node = parent, parent = ((node + 1) >>> 1) - 1
) {
swap(this.#heap, node, parent);
}
}
#siftDown(): void;
#siftDown(size = this.size, node = 0, isGreater = this.#isGreater): void {
while (true) {
const leftNode = (node << 1) + 1;
const rightNode = leftNode + 1;
if (
(leftNode >= size || isGreater(node, leftNode)) &&
(rightNode >= size || isGreater(node, rightNode))
) {
break;
}
const maxChild =
rightNode < size && isGreater(rightNode, leftNode)
? rightNode
: leftNode;
swap(this.#heap, node, maxChild);
node = maxChild;
}
}
}
使用方法：
const numberComparator: Comparator<number> = (numberA, numberB) => {
return numberA - numberB;
};
const queue = new PriorityQueue(numberComparator);
queue.add(10);
queue.add(30);
queue.add(20);
while (queue.size) {
console.log(queue.poll());
}
2n的空间，因为多维数组中的每一行只有两个元素（固定长度）。 - gyreif (bottom > top) this._swap(top, bottom);这样的语句拆成两行（还有 1TBS，我强烈建议在教程代码中使用，但那是另一个话题），2. 使用临时变量来存储需要重复计算的值（特别是如果它们是循环中使用的函数调用的结果），例如你的left(node)、right(node)、this.size()等等... 在 JS/ES 代码中，这仍然会 真正 影响速度。 - user719662n >>> 1相当于除以2并向下取整，而n << 1相当于乘以2，并且只有在需要保持奇偶性时才会选择它，而不是2*n。 - gyresort()函数所期望的签名：https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort - wvdz