在最近發(fā)布的 .NET 6 中抖剿，包含了一個(gè)新的數(shù)據(jù)結(jié)構(gòu)召夹，優(yōu)先隊(duì)列 PriorityQueue双揪， 實(shí)際上這個(gè)數(shù)據(jù)結(jié)構(gòu)在隔壁 Java中已經(jīng)存在了很多年了, 那優(yōu)先隊(duì)列是怎么實(shí)現(xiàn)的呢? 讓我們來一探究竟吧木蹬。
時(shí)間復(fù)雜度
因?yàn)榻酉聛頃治鰰r(shí)間復(fù)雜度, 這里先貼一張幾種時(shí)間復(fù)雜度的對比圖，從低階到高階有：O(1)亲怠、O(logn)所计、O(n)、O(nlogn)团秽、O(n2 )主胧。
什么是優(yōu)先隊(duì)列
首先，隊(duì)列大家都知道, 是一個(gè)非诚扒冢基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu), 它的特點(diǎn)是先進(jìn)先出（FIFO）讥裤。
而優(yōu)先隊(duì)列卻不一定是先進(jìn)先出，因?yàn)槊總€(gè)元素都有一個(gè)權(quán)重值, 代表著元素出隊(duì)的優(yōu)先級姻报。
隊(duì)列可以用數(shù)組和鏈表實(shí)現(xiàn), 簡單、高效, 這樣入隊(duì)和出隊(duì)的時(shí)間復(fù)雜度都是 O(1)间螟。
優(yōu)先隊(duì)列能不能使用上面的方法呢吴旋？ 也可以, 但是每次新元素入隊(duì)后, 需要和隊(duì)列內(nèi)的元素進(jìn)行遍歷和大小對比, 然后插入到合適的位置, 讓整個(gè)序列保持從大到小或者從小到大，這樣入隊(duì)的時(shí)間復(fù)雜度變成 O(n)厢破， 而出隊(duì)復(fù)雜度不變, 還是 O(1)荣瑟。O(n) 代表入隊(duì)的時(shí)間是線性增長的, 效率較低, 有沒有更高效的方法呢？
堆 Heap
堆這種數(shù)據(jù)結(jié)構(gòu)的應(yīng)用場景非常多摩泪，最經(jīng)典的莫過于堆排序了, 堆排序是一種原地的笆焰、時(shí)間復(fù)雜度為 O(nlog n) 的排序算法，另外见坑，堆也很適合用來做優(yōu)先隊(duì)列嚷掠。
堆和樹的結(jié)構(gòu)其實(shí)是相似的, 堆有二叉堆, d-ary 堆, 2-3 堆, 斐波那契堆等等, 堆有一個(gè)特點(diǎn)就是每個(gè)父節(jié)點(diǎn)都大于等于它的兒子節(jié)點(diǎn), 這種是大頂堆, 或者每個(gè)父節(jié)點(diǎn)都小于等于它的兒子節(jié)點(diǎn), 這種是小頂堆捏检，另外堆的兒子不分左右, 其中 java 中的 PriorityQueue 就是用二叉小頂堆實(shí)現(xiàn)的。
上面就是二叉堆, 而 .NET 6 中的 PriorityQueue 是由 d-ary 堆實(shí)現(xiàn)的, 而 d 表示父節(jié)點(diǎn)有幾個(gè)兒子節(jié)點(diǎn), .NET 6 中指定這個(gè)值為4不皆，并且是小頂堆贯城，也就是 “四叉小頂堆"。
四叉堆比二叉堆更快霹娄，可以參考下面鏈接的論文
A Back-to-Basics Empirical Study of Priority Queues
那么如何在代碼中實(shí)現(xiàn)呢能犯？其實(shí)可以用數(shù)組存儲堆, 我們可以通過”廣度優(yōu)先遍歷“ 的方法, 把堆的節(jié)點(diǎn)映射到一個(gè)數(shù)組中，如下
另外犬耻，堆和數(shù)組之間還有下面的關(guān)系
堆的頂點(diǎn)就是數(shù)組的第一個(gè)元素踩晶，也是最小的元素。
通過子節(jié)點(diǎn)的下標(biāo)枕磁，就可以通過公式計(jì)算出父節(jié)點(diǎn)的下標(biāo), 公式為
P = (C - 1) / 4
其中 P = 父節(jié)點(diǎn)的下標(biāo), C = 子節(jié)點(diǎn)的下標(biāo)
現(xiàn)在優(yōu)先隊(duì)列的數(shù)據(jù)結(jié)構(gòu)確定了, 接下來看元素的入隊(duì)和出隊(duì)渡蜻。
入隊(duì) Enqueue
使用堆來實(shí)現(xiàn)優(yōu)先隊(duì)列，入隊(duì)操作2步完成, 非常簡單透典！
添加新節(jié)點(diǎn)到末尾
通過上面的公式?P = (C - 1) / 4, 新的子節(jié)點(diǎn)和父節(jié)點(diǎn)進(jìn)行大小對比晴楔，如果子節(jié)點(diǎn)比較小，那么就和父節(jié)點(diǎn)交換峭咒，重復(fù)這個(gè)過程税弃，直到子節(jié)點(diǎn)大于或等于父節(jié)點(diǎn)，或者子節(jié)點(diǎn)變成堆頂凑队，堆化完成, 這個(gè)交換過程是從下往上的, 入隊(duì)的時(shí)間復(fù)雜度是 O(log n)则果。
出隊(duì) Dequeue
出隊(duì)，就是每次取隊(duì)列內(nèi)最小的元素漩氨，基小頂堆結(jié)構(gòu)西壮，其實(shí)只需要取堆頂?shù)脑丶纯桑瑢?yīng)數(shù)組的第1個(gè)元素 array[0]叫惊。
你會發(fā)現(xiàn)款青，當(dāng)取出堆頂元素以后，小頂堆的頂已經(jīng)空了, 為了保持堆的結(jié)構(gòu)霍狰，我們需要重新堆化抡草。
和上面的入隊(duì) Enqueue 的邏輯有異曲同工之妙, 我們可以取堆的最后一個(gè)元素，把它放到堆頂, 然后父節(jié)點(diǎn)去和4個(gè)兒子節(jié)點(diǎn)比大小蔗坯，如果比兒子節(jié)點(diǎn)大康震，就交換， 重復(fù)這個(gè)過程宾濒，直到父節(jié)點(diǎn)比4個(gè)兒子節(jié)點(diǎn)都大, 或者到達(dá)堆的最后一層腿短，堆化完成，這個(gè)交換過程是從上往下的,出隊(duì)的時(shí)間復(fù)雜度同樣是 O(log n)。
另外橘忱，如果多個(gè)兒子節(jié)點(diǎn)都比父節(jié)點(diǎn)小赴魁，那父節(jié)點(diǎn)和最小的子節(jié)點(diǎn)交換。
擴(kuò)容和收縮機(jī)制
優(yōu)先隊(duì)列是用數(shù)組實(shí)現(xiàn)的四叉小頂堆, 那么就存在數(shù)組的擴(kuò)容和收縮的情況
擴(kuò)容：最小為4鹦付，數(shù)組滿的時(shí)候會擴(kuò)大為當(dāng)前容量的2倍尚粘。
收縮：數(shù)組不會自動(dòng)收縮，不過可以手動(dòng)調(diào)用 TrimExcess() 方法, 當(dāng)空余的空間大于10% 的時(shí)候, 數(shù)組的長度會收縮到當(dāng)前隊(duì)列元素的數(shù)量敲长。
總結(jié)
本文主要介紹了 .NET 6 新增的數(shù)據(jù)結(jié)構(gòu)優(yōu)先隊(duì)列郎嫁，感興趣的也可以看一下 PriorityQueue 的源碼, 其實(shí)就是基于堆這種結(jié)構(gòu)實(shí)現(xiàn)的，也展示了入隊(duì)和出隊(duì)的堆結(jié)構(gòu)的變化過程祈噪，另外需要注意的是泽铛，堆這種結(jié)構(gòu)不是穩(wěn)定的，因?yàn)樵谂判虻倪^程辑鲤，存在將堆的最后一個(gè)節(jié)點(diǎn)跟堆頂節(jié)點(diǎn)互換的操作盔腔，所以以相同優(yōu)先級入隊(duì)的元素并不能保證以相同的順序出隊(duì)。
