在刷leetcode算法題的時(shí)候偶然間發(fā)現(xiàn)了一種非常好用的數(shù)據(jù)結(jié)構(gòu)——優(yōu)先隊(duì)列，與普通隊(duì)列不同的是它會(huì)在你插入時(shí)就幫你根據(jù)優(yōu)先級對數(shù)據(jù)進(jìn)行排序，底層實(shí)現(xiàn)是用了堆排序奕纫。
在很多語言中其實(shí)都有內(nèi)置（或者在常用庫中有）這種數(shù)據(jù)結(jié)構(gòu)署惯，如果是使用js的話是需要先安裝對應(yīng)的依賴：
npm install --save @datastructures-js/priority-queue
引入方式
import {
PriorityQueue, // 優(yōu)先隊(duì)列又官，可自定義排序方式延刘，較為靈活
MinPriorityQueue, // 最大優(yōu)先隊(duì)列
MaxPriorityQueue, // 最小優(yōu)先隊(duì)列
ICompare, // 比較的方法的類型
IGetCompareValue, // 比較的值的類型
} from '@datastructures-js/priority-queue';
PriorityQueue
首先要介紹的就是優(yōu)先隊(duì)列這個(gè)類，創(chuàng)建它的實(shí)例時(shí)需要傳入一個(gè)函數(shù)六敬，類似于sort的回調(diào)函數(shù)碘赖，返回大于0的數(shù)表示兩項(xiàng)需要互換位置。
interface ICar {
year: number;
price: number;
}
// 這個(gè)比較函數(shù)表示年份最大（最新）優(yōu)先外构，若相等則價(jià)格最小優(yōu)先
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
最大普泡、最小優(yōu)先隊(duì)列則不需要傳入一個(gè)比較函數(shù)，只需要指定進(jìn)行比較的對象即可审编，若元素為數(shù)字劫哼、字符串等原始變量，創(chuàng)建時(shí)不需要傳入比較函數(shù)
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(); // 不傳則直接比較元素割笙，最小優(yōu)先
fromArray
fromArray是這三個(gè)類上的一個(gè)方法，可以在O(n)的時(shí)間復(fù)雜度上將一個(gè)數(shù)組轉(zhuǎn)化為優(yōu)先隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)：
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)
這三個(gè)類中插入元素的方法眯亦，使用enqueue(push是別名伤溉，效果一樣)，可以以O(shè)(log(n))的復(fù)雜度插入數(shù)據(jù)：
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方法可以獲取當(dāng)前隊(duì)列中優(yōu)先級最高的那一項(xiàng)：
console.log(carsQueue.front()); // { year: 2022, price: 70000 }
console.log(numbersQueue.front()); // -5
console.log(bidsQueue.front()); // { id: 2, value: 20000 }
back
back方法可以獲取當(dāng)前隊(duì)列中優(yōu)先級最低的那一項(xiàng)：
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)方法的效果是返回并移除隊(duì)列中優(yōu)先級最高的一項(xiàng)（即出列）妻率，時(shí)間復(fù)雜度同樣是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方法需要傳入一個(gè)比較函數(shù)乱顾，效果是返回并移除符合條件的項(xiàng)，時(shí)間復(fù)雜度是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方法可以用來判斷隊(duì)列是否為空：
console.log(carsQueue.isEmpty()); // false
console.log(numbersQueue.isEmpty()); // false
console.log(bidsQueue.isEmpty()); // false
size
size方法可以用來返回隊(duì)列中項(xiàng)的個(gè)數(shù)：
console.log(carsQueue.size()); // 3
console.log(numbersQueue.size()); // 3
console.log(bidsQueue.size()); // 3
toArray
toArray方法可以在O(n*log(n))的時(shí)間復(fù)雜度下將優(yōu)先隊(duì)列數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)為普通的數(shù)組：
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方法可以清空整個(gè)隊(duì)列：
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
優(yōu)先隊(duì)列這一數(shù)據(jù)結(jié)構(gòu)也實(shí)現(xiàn)Symbol.iterator這一遍歷器接口宫静，可以進(jìn)行相關(guān)展開走净、循環(huán)操作：
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
使用場景
奉上一個(gè)LeetCode題目（2208. 將數(shù)組和減半的最少操作次數(shù)）：
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;
};
