數(shù)據(jù)結(jié)構(gòu)-優(yōu)先隊(duì)列(priority-queue)

在刷leetcode算法題的時(shí)候偶然間發(fā)現(xiàn)了一種非常好用的數(shù)據(jù)結(jié)構(gòu)——優(yōu)先隊(duì)列，與普通隊(duì)列不同的是它會(huì)在你插入時(shí)就幫你根據(jù)優(yōu)先級(jí)對(duì)數(shù)據(jù)進(jìn)行排序，底層實(shí)現(xiàn)是用了堆排序。
在很多語(yǔ)言中其實(shí)都有內(nèi)置（或者在常用庫(kù)中有）這種數(shù)據(jù)結(jié)構(gòu)，如果是使用js的話是需要先安裝對(duì)應(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)行比較的對(duì)象即可，若元素為數(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)先級(jí)最高的那一項(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)先級(jí)最低的那一項(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)先級(jí)最高的一項(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方法可以用來(lái)判斷隊(duì)列是否為空：

console.log(carsQueue.isEmpty()); // false
console.log(numbersQueue.isEmpty()); // false
console.log(bidsQueue.isEmpty()); // false

size

size方法可以用來(lái)返回隊(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)展開(kāi)、循環(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

使用場(chǎng)景

奉上一個(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;
};
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容