在刷leetcode算法题的时候偶然间发现了一种非常好用的数据结构——优先队列，与普通队列不同的是它会在你插入时就帮你根据优先级对数据进行排序，底层实现是用了堆排序。
在很多语言中其实都有内置（或者在常用库中有）这种数据结构，如果是使用js的话是需要先安装对应的依赖：
npm install --save @datastructures-js/priority-queue
引入方式
import {
PriorityQueue, // 优先队列，可自定义排序方式，较为灵活
MinPriorityQueue, // 最大优先队列
MaxPriorityQueue, // 最小优先队列
ICompare, // 比较的方法的类型
IGetCompareValue, // 比较的值的类型
} from '@datastructures-js/priority-queue';
PriorityQueue
首先要介绍的就是优先队列这个类，创建它的实例时需要传入一个函数，类似于sort的回调函数，返回大于0的数表示两项需要互换位置。
interface ICar {
year: number;
price: number;
}
// 这个比较函数表示年份最大（最新）优先，若相等则价格最小优先
const compareCars: ICompare<ICar> = (a: ICar, b: ICar) => {
if (a.year > b.year) {
return -1;
}
if (a.year < b.year) {
return 1;
}
return a.price < b.price ? -1 : 1;
};
const carsQueue = new PriorityQueue<ICar>(compareCars);
MinPriorityQueue, MaxPriorityQueue
最大、最小优先队列则不需要传入一个比较函数，只需要指定进行比较的对象即可，若元素为数字、字符串等原始变量，创建时不需要传入比较函数
const numbersQueue = new MinPriorityQueue<number>();
interface IBid {
id: number;
value: number;
}
const getBidValue: IGetCompareValue<IBid> = (bid) => bid.value;
const bidsQueue = new MaxPriorityQueue<IBid>(getBidValue);
const numbersQueue = new MinPriorityQueue(); // 不传则直接比较元素，最小优先
fromArray
fromArray是这三个类上的一个方法，可以在O(n)的时间复杂度上将一个数组转化为优先队列这种数据结构：
PriorityQueue
const numbers = [3, -2, 5, 0, -1, -5, 4];
const pq = PriorityQueue.fromArray<number>(numbers, (a, b) => a - b);
console.log(numbers); // [-5, -1, -2, 3, 0, 5, 4]
pq.dequeue(); // -5
pq.dequeue(); // -2
pq.dequeue(); // -1
console.log(numbers); // [ 0, 3, 4, 5 ]
MinPriorityQueue, MaxPriorityQueue
const numbers = [3, -2, 5, 0, -1, -5, 4];
const mpq = MaxPriorityQueue.fromArray<number>(numbers);
console.log(numbers); // [-5, -1, -2, 3, 0, 5, 4]
mpq.dequeue(); // 5
mpq.dequeue(); // 4
mpq.dequeue(); // 3
console.log(numbers); // [ 0, -1, -5, -2 ]
enqueue (push)
这三个类中插入元素的方法，使用enqueue(push是别名，效果一样)，可以以O(log(n))的复杂度插入数据：
const cars = [
{ year: 2013, price: 35000 },
{ year: 2010, price: 2000 },
{ year: 2013, price: 30000 },
{ year: 2017, price: 50000 },
{ year: 2013, price: 25000 },
{ year: 2015, price: 40000 },
{ year: 2022, price: 70000 }
];
cars.forEach((car) => carsQueue.enqueue(car));
const numbers = [3, -2, 5, 0, -1, -5, 4];
numbers.forEach((num) => numbersQueue.push(num)); // push is an alias for enqueue
const bids = [
{ id: 1, value: 1000 },
{ id: 2, value: 20000 },
{ id: 3, value: 1000 },
{ id: 4, value: 1500 },
{ id: 5, value: 12000 },
{ id: 6, value: 4000 },
{ id: 7, value: 8000 }
];
bids.forEach((bid) => bidsQueue.enqueue(bid));
front
front方法可以获取当前队列中优先级最高的那一项：
console.log(carsQueue.front()); // { year: 2022, price: 70000 }
console.log(numbersQueue.front()); // -5
console.log(bidsQueue.front()); // { id: 2, value: 20000 }
back
back方法可以获取当前队列中优先级最低的那一项：
console.log(carsQueue.back()); // { year: 2010, price: 2000 }
console.log(numbersQueue.back()); // 5
console.log(bidsQueue.back()); // { id: 1, value: 1000 }
dequeue (pop)
dequeue(别名pop)方法的效果是返回并移除队列中优先级最高的一项（即出列），时间复杂度同样是O(log(n))：
console.log(carsQueue.dequeue()); // { year: 2022, price: 70000 }
console.log(carsQueue.dequeue()); // { year: 2017, price: 50000 }
console.log(carsQueue.dequeue()); // { year: 2015, price: 40000 }
console.log(numbersQueue.dequeue()); // -5
console.log(numbersQueue.dequeue()); // -2
console.log(numbersQueue.dequeue()); // -1
console.log(bidsQueue.pop()); // { id: 2, value: 20000 }
console.log(bidsQueue.pop()); // { id: 5, value: 12000 }
console.log(bidsQueue.pop()); // { id: 7, value: 8000 }
remove
remove方法需要传入一个比较函数，效果是返回并移除符合条件的项，时间复杂度是O(n*log(n))：
carsQueue.remove((car) => car.price === 35000); // [{ year: 2013, price: 35000 }]
numbersQueue.remove((n) => n === 4); // [4]
bidsQueue.remove((bid) => bid.id === 3); // [{ id: 3, value: 1000 }]
isEmpty
isEmpty方法可以用来判断队列是否为空：
console.log(carsQueue.isEmpty()); // false
console.log(numbersQueue.isEmpty()); // false
console.log(bidsQueue.isEmpty()); // false
size
size方法可以用来返回队列中项的个数：
console.log(carsQueue.size()); // 3
console.log(numbersQueue.size()); // 3
console.log(bidsQueue.size()); // 3
toArray
toArray方法可以在O(n*log(n))的时间复杂度下将优先队列数据结构转为普通的数组：
console.log(carsQueue.toArray());
/*
[
{ year: 2013, price: 25000 },
{ year: 2013, price: 30000 },
{ year: 2010, price: 2000 }
]
*/
console.log(numbersQueue.toArray()); // [ 0, 3, 5 ]
console.log(bidsQueue.toArray());
/*
[
{ id: 6, value: 4000 },
{ id: 4, value: 1500 },
{ id: 1, value: 1000 }
]
*/
clear
clear方法可以清空整个队列：
carsQueue.clear();
console.log(carsQueue.size()); // 0
console.log(carsQueue.front()); // null
console.log(carsQueue.dequeue()); // null
console.log(carsQueue.isEmpty()); // true
numbersQueue.clear();
console.log(numbersQueue.size()); // 0
console.log(numbersQueue.front()); // null
console.log(numbersQueue.dequeue()); // null
console.log(numbersQueue.isEmpty()); // true
bidsQueue.clear();
console.log(bidsQueue.size()); // 0
console.log(bidsQueue.front()); // null
console.log(bidsQueue.dequeue()); // null
console.log(bidsQueue.isEmpty()); // true
Symbol.iterator
优先队列这一数据结构也实现Symbol.iterator这一遍历器接口，可以进行相关展开、循环操作：
console.log([...carsQueue]);
/*
[
{ year: 2013, price: 25000 },
{ year: 2013, price: 30000 },
{ year: 2010, price: 2000 }
]
*/
console.log(carsQueue.size()); // 0
console.log([...numbersQueue]); // [ 0, 3, 5 ]
console.log(numbersQueue.size()); // 0
for (const bid of bidsQueue) {
console.log(bid);
}
/*
{ id: 6, value: 4000 },
{ id: 4, value: 1500 },
{ id: 1, value: 1000 }
*/
console.log(bidsHeap.size()); // 0
使用场景
奉上一个LeetCode题目（2208. 将数组和减半的最少操作次数）：
var halveArray = function(nums) {
const pq = new MaxPriorityQueue();
for (const num of nums) {
pq.enqueue(num);
}
let res = 0;
let sum1 = nums.reduce((acc, curr) => acc + curr, 0);
let sum2 = 0;
while (sum2 < sum1 / 2) {
const x = pq.dequeue().element;
sum2 += x / 2;
pq.enqueue(x / 2);
res++;
}
return res;
};
