先隊(duì)列）專題精講：一個(gè)中心、兩種實(shí)現(xiàn)、三個(gè)技巧與四大應(yīng)用)
LeetCode 堆優(yōu)先隊(duì)列專題精講一個(gè)中心、兩種實(shí)現(xiàn)、三個(gè)技巧與四大應(yīng)用【免費(fèi)下載鏈接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode題解記錄自己的leetcode解題之路。)項(xiàng)目地址: https://gitcode.com/gh_mirrors/le/leetcode本文源自 thinkings/heap.en.md堆專題第一講及其續(xù)篇 thinkings/heap-2.en.md堆專題第二講三個(gè)技巧。它系統(tǒng)梳理了「堆/優(yōu)先隊(duì)列」這一數(shù)據(jù)結(jié)構(gòu)的適用場(chǎng)景、核心原理、實(shí)現(xiàn)方式與解題套路是刷 LeetCode 堆類題目官方標(biāo)簽約 42 道困難度接近 50%之前值得先讀的專題總綱。讀完本文你將掌握用「動(dòng)態(tài)求極值」這一中心思想識(shí)別堆題、用跳表與二叉堆兩種視角理解堆的底層原理、以及多路歸并、固定堆等直接可用的解題模板。說(shuō)明本文中「堆」與「優(yōu)先隊(duì)列」不做區(qū)分二者可視為同一事物除非特別說(shuō)明本文所說(shuō)的堆均指小頂堆即堆頂為最小值父節(jié)點(diǎn)權(quán)值不大于子節(jié)點(diǎn)權(quán)值。一點(diǎn)絮叨為什么值得專門開(kāi)一個(gè)堆專題堆在 LeetCode 中被單獨(dú)打上了標(biāo)簽。從官方難度標(biāo)簽來(lái)看堆的題目一共 42 道其中困難題占比將近 50%作為對(duì)比樹(shù)專題的困難度只有不到 10%從通過(guò)率來(lái)看一半以上的堆題目平均通過(guò)率在 50% 以下而樹(shù)專題通過(guò)率在 50% 以下的只有不到三分之一。因此堆確實(shí)是一個(gè)難度不低的專題。為此本專題的核心方法論被提煉為一句話口訣一個(gè)中心兩種實(shí)現(xiàn)三個(gè)技巧四大應(yīng)用。一個(gè)中心動(dòng)態(tài)求極值。兩種實(shí)現(xiàn)跳表實(shí)現(xiàn)與二叉堆實(shí)現(xiàn)。三個(gè)技巧多路歸并、固定堆、事后小諸葛。四大應(yīng)用topK、帶權(quán)最短距離、因子分解、堆排序。下文將沿著這條主線逐一展開(kāi)既講實(shí)現(xiàn)與原理更講問(wèn)題背后的背景、套路與模板。堆的使用場(chǎng)景從「掛號(hào)系統(tǒng)」說(shuō)起堆是一種數(shù)據(jù)結(jié)構(gòu)而數(shù)據(jù)結(jié)構(gòu)是為算法服務(wù)的。學(xué)習(xí)堆要解決的第一個(gè)問(wèn)題是堆到底解決什么問(wèn)題、適用于什么場(chǎng)景這里給出的學(xué)習(xí)建議是先不要糾結(jié)堆怎么實(shí)現(xiàn)的先了解堆解決了什么問(wèn)題。當(dāng)你理解了使用背景之后先當(dāng)一個(gè)「調(diào)包俠」直接用現(xiàn)成的堆 API 解決問(wèn)題等理解得差不多了再回頭去看堆的原理和實(shí)現(xiàn)。為了說(shuō)明堆的使用場(chǎng)景這里虛構(gòu)了一個(gè)場(chǎng)景——排隊(duì)掛號(hào)系統(tǒng)。下面這個(gè)例子很重要后面會(huì)反復(fù)與它對(duì)比。問(wèn)題描述假如你是一個(gè)排隊(duì)掛號(hào)系統(tǒng)的技術(shù)負(fù)責(zé)人。該系統(tǒng)需要給每一個(gè)前來(lái)排隊(duì)的人發(fā)放一個(gè)排隊(duì)碼入隊(duì)并根據(jù)先來(lái)后到的原則進(jìn)行叫號(hào)出隊(duì)。除此之外系統(tǒng)還區(qū)分了幾種客戶類型普通客戶、VIP 客戶、至尊 VIP 客戶。由此衍生出兩個(gè)設(shè)計(jì)問(wèn)題問(wèn)題一如果不同的客戶使用不同的窗口VIP 客戶由專家醫(yī)生服務(wù)普通客戶由普通醫(yī)生服務(wù)系統(tǒng)該如何設(shè)計(jì)實(shí)現(xiàn)問(wèn)題二如果不同的客戶都使用同一個(gè)窗口服務(wù)內(nèi)容相同但優(yōu)先級(jí)不同比如同時(shí)來(lái)掛號(hào)的 VIP 客戶優(yōu)先級(jí)高于普通客戶系統(tǒng)又該如何設(shè)計(jì)實(shí)現(xiàn)初步的解決方案如果不同的客戶使用不同的窗口那么可以設(shè)計(jì)三個(gè)隊(duì)列分別存放正在排隊(duì)的三種人。這種設(shè)計(jì)滿足要求也足夠簡(jiǎn)單。如果只有一個(gè)窗口所有病人需要使用同一個(gè)隊(duì)列且相同客戶類型內(nèi)部按照先到先服務(wù)原則但不同客戶類型之間允許插隊(duì)。簡(jiǎn)單起見(jiàn)引入虛擬時(shí)間的概念普通客戶的虛擬時(shí)間就是真實(shí)時(shí)間VIP 客戶的虛擬時(shí)間 實(shí)際到達(dá)時(shí)間 ? 1 小時(shí)例如 14:00 到達(dá)視為 13:00 到達(dá)至尊 VIP 客戶的虛擬時(shí)間 實(shí)際到達(dá)時(shí)間 ? 2 小時(shí)例如 14:00 到達(dá)視為 12:00 到達(dá)。這樣系統(tǒng)只需要按照「虛擬到達(dá)時(shí)間」進(jìn)行先到先服務(wù)即可——繼續(xù)使用三個(gè)隊(duì)列的方式只不過(guò)隊(duì)列里存儲(chǔ)的不是真實(shí)時(shí)間而是虛擬時(shí)間每次叫號(hào)時(shí)比較虛擬時(shí)間虛擬時(shí)間較小的先服務(wù)。不難看出隊(duì)列內(nèi)部的時(shí)間都是有序的。而這里的虛擬時(shí)間其實(shí)就是優(yōu)先隊(duì)列中的「優(yōu)先權(quán)重」——虛擬時(shí)間越小權(quán)重越大。可以插隊(duì)怎么辦上述算法能很好地完成需求但新的產(chǎn)品需求出現(xiàn)了別的門診的病人轉(zhuǎn)院到本診所按照他之前的排隊(duì)信息計(jì)算例如 12:00 在別的院掛的號(hào)轉(zhuǎn)到本院仍按 12:00 掛號(hào)算被叫到號(hào)三分鐘沒(méi)有應(yīng)答的作廢但如果病人重新回來(lái)則按「當(dāng)前時(shí)間 ? 1 小時(shí)」作為虛擬時(shí)間重新排隊(duì)。這樣就出現(xiàn)了「插隊(duì)」的情況。一個(gè)簡(jiǎn)單的做法是將其插入到正確位置并重新調(diào)整后面所有人的排隊(duì)位置。如果隊(duì)列用數(shù)組實(shí)現(xiàn)插隊(duì)過(guò)程的時(shí)間復(fù)雜度為 $O(N)$其中 $N$ 為被插隊(duì)的隊(duì)伍長(zhǎng)度隊(duì)伍很長(zhǎng)時(shí)調(diào)整次數(shù)明顯增加。本質(zhì)上我們是在維護(hù)一個(gè)有序列表數(shù)組方式的好處是隨機(jī)訪問(wèn)但這個(gè)需求并不需要該特性用鏈表實(shí)現(xiàn)插入理論上是 $O(1)$但定位插入位置需要遍歷查找復(fù)雜度又退化為 $O(N)$。有沒(méi)有時(shí)間復(fù)雜度更好的做法答案就是本文的主角——優(yōu)先隊(duì)列。有序鏈表的查找可以優(yōu)化由于是有序的可以用跳表加速查找時(shí)間復(fù)雜度可優(yōu)化到 $O(\log N)$。事實(shí)上算法界有很多類似的問(wèn)題例如數(shù)據(jù)庫(kù)索引給有序的列添加索引時(shí)不能每次插入一條數(shù)據(jù)都調(diào)整所有數(shù)據(jù)因此可以用平衡樹(shù)來(lái)實(shí)現(xiàn)每次插入最多調(diào)整 $O(\log N)$ 個(gè)節(jié)點(diǎn)。優(yōu)先隊(duì)列的另外一種實(shí)現(xiàn)——二叉堆正是這個(gè)思想時(shí)間復(fù)雜度同樣可以優(yōu)化到 $O(\log N)$。使用堆解決問(wèn)題堆的兩個(gè)核心 API 是push和pop。先把它想象成一個(gè)黑盒push推入一個(gè)數(shù)據(jù)內(nèi)部怎么組織不用管對(duì)應(yīng)場(chǎng)景中的排隊(duì)和插隊(duì)pop彈出一個(gè)數(shù)據(jù)彈出的數(shù)據(jù)一定是最小的內(nèi)部怎么實(shí)現(xiàn)不用管對(duì)應(yīng)場(chǎng)景中的叫號(hào)。這里的例子是小頂堆如果彈出的數(shù)據(jù)一定是最大的則對(duì)應(yīng)大頂堆的實(shí)現(xiàn)。借助這兩個(gè) API 就能實(shí)現(xiàn)上面的需求Python 的heapq寫(xiě)法如下# 12:00 來(lái)了一個(gè)普通的顧客push heapq.heappush(normal_pq, 12:00) # 12:30 來(lái)了一個(gè)普通顧客push heapq.heappush(normal_pq, 12:30) # 13:00 來(lái)了一個(gè)普通顧客push heapq.heappush(normal_pq, 13:00) # 插隊(duì)push時(shí)間復(fù)雜度可以達(dá)到 O(logN)。如何做到先不管我們先會(huì)用就行。 heapq.heappush(normal_pq, 12:20) # 叫號(hào)pop。12:00 來(lái)的先被叫到。注意這里彈出時(shí)間復(fù)雜度也變成了 O(logN)。 heapq.heappop(normal_pq)小結(jié)上面這個(gè)場(chǎng)景單純使用數(shù)組和鏈表都可以滿足需求但在應(yīng)對(duì)「插隊(duì)」時(shí)表現(xiàn)各異若永遠(yuǎn)維護(hù)一個(gè)有序數(shù)組取極值很容易但插隊(duì)麻煩$O(N)$若永遠(yuǎn)維護(hù)一個(gè)有序鏈表取極值也容易但要想查找足夠快而不是線性掃描就需要借助索引對(duì)應(yīng)優(yōu)先隊(duì)列的跳表實(shí)現(xiàn)若永遠(yuǎn)維護(hù)一棵樹(shù)根節(jié)點(diǎn)即極值$O(1)$ 可取到極值但調(diào)整過(guò)程需要 $O(\log N)$對(duì)應(yīng)優(yōu)先隊(duì)列的二叉堆實(shí)現(xiàn)。一句話總結(jié)堆就是動(dòng)態(tài)幫你求極值的。當(dāng)你需要?jiǎng)討B(tài)求最大或最小值時(shí)就用它。具體怎么實(shí)現(xiàn)、復(fù)雜度如何分析后面再講現(xiàn)在只需記住使用場(chǎng)景、堆如何解決這些問(wèn)題以及堆的 API 即可。隊(duì)列 VS 優(yōu)先隊(duì)列隊(duì)列只是一種特殊的優(yōu)先隊(duì)列在講具體實(shí)現(xiàn)之前有必要回答一個(gè)普遍關(guān)心的問(wèn)題優(yōu)先隊(duì)列是隊(duì)列嗎很多人認(rèn)為隊(duì)列和優(yōu)先隊(duì)列是完全不同的東西。但本專題的觀點(diǎn)不同普通的隊(duì)列也可以看成是一個(gè)特殊的優(yōu)先級(jí)隊(duì)列——隊(duì)列無(wú)非就是以「時(shí)間」這一變量作為優(yōu)先級(jí)的優(yōu)先隊(duì)列時(shí)間越早優(yōu)先級(jí)越高越先出隊(duì)。這與網(wǎng)上大多數(shù)「優(yōu)先級(jí)隊(duì)列和隊(duì)列沒(méi)什么關(guān)系」的說(shuō)法有所區(qū)別。平時(shí)寫(xiě) BFS 時(shí)都會(huì)用到隊(duì)列來(lái)處理節(jié)點(diǎn)的訪問(wèn)順序。那使用優(yōu)先隊(duì)列行不行當(dāng)然可以以 513. 找樹(shù)左下角的值 為例。例題513. 找樹(shù)左下角的值題目描述定一個(gè)二叉樹(shù)在樹(shù)的最后一行找到最左邊的值。 示例 1: 輸入: 2 / \ 1 3 輸出: 1 示例 2: 輸入: 1 / \ 2 3 / / \ 4 5 6 / 7 輸出: 7 注意: 您可以假設(shè)樹(shù)即給定的根節(jié)點(diǎn)不為 NULL。思路可以使用 BFS 做一次層次遍歷并且每一層都從右向左遍歷這樣層次遍歷的最后一個(gè)節(jié)點(diǎn)就是樹(shù)左下角的節(jié)點(diǎn)。常規(guī)做法是使用雙端隊(duì)列普通隊(duì)列實(shí)現(xiàn)利用先進(jìn)先出的原則很方便地實(shí)現(xiàn)層次遍歷。代碼普通隊(duì)列版class Solution: def findBottomLeftValue(self, root: TreeNode) - int: if root is None: return None queue collections.deque([root]) ans None while queue: size len(queue) for _ in range(size): ans node queue.popleft() if node.right: queue.append(node.right) if node.left: queue.append(node.left) return ans.val代碼優(yōu)先隊(duì)列版實(shí)際上也可以使用優(yōu)先隊(duì)列思路和代碼幾乎與上面完全一樣class Solution: def findBottomLeftValue(self, root: TreeNode) - int: if root is None: return None queue [] # 堆存儲(chǔ)三元組(a,b,c)a 表示層級(jí)b 表示節(jié)點(diǎn)編號(hào)以完全二叉樹(shù)的形式編號(hào)空節(jié)點(diǎn)也編號(hào)c 是節(jié)點(diǎn)本身 heapq.heappush(queue, (1, 1, root)) ans None while queue: size len(queue) for _ in range(size): level, i, node heapq.heappop(queue) ans node if node.right: heapq.heappush(queue, (level 1, 2 * i 1, node.right)) if node.left: heapq.heappush(queue, (level 1, 2 * i 2, node.left)) return ans.val小結(jié)所有使用隊(duì)列的地方都可以使用優(yōu)先隊(duì)列來(lái)完成反之卻不一定。那既然優(yōu)先隊(duì)列這么厲害為什么平時(shí)用隊(duì)列的地方?jīng)]人用堆最核心的原因是時(shí)間復(fù)雜度更差上面的例子中本來(lái)入隊(duì)和出隊(duì)都可以在 $O(1)$ 時(shí)間完成而現(xiàn)在入隊(duì)和出隊(duì)的復(fù)雜度都是 $O(\log N)$$N$ 為當(dāng)前隊(duì)列大小。因此在沒(méi)有必要的地方使用堆會(huì)大大提高算法的時(shí)間復(fù)雜度。不過(guò) BFS 真的沒(méi)人用優(yōu)先隊(duì)列實(shí)現(xiàn)嗎當(dāng)然不是比如帶權(quán)圖的最短路徑問(wèn)題用隊(duì)列做 BFS 就需要優(yōu)先隊(duì)列因?yàn)槁窂街g有權(quán)重的差異——這正是優(yōu)先隊(duì)列的設(shè)計(jì)初衷。使用優(yōu)先隊(duì)列的 BFS 最典型的就是dijkstra 算法。這再次印證了那句話隊(duì)列就是一種特殊的優(yōu)先隊(duì)列特殊到權(quán)重就是按照到來(lái)的順序定誰(shuí)先來(lái)誰(shuí)的優(yōu)先級(jí)高在這種特殊情況下不必維護(hù)堆從而獲得更好的時(shí)間復(fù)雜度。一個(gè)中心動(dòng)態(tài)求極值堆的問(wèn)題核心點(diǎn)就一個(gè)動(dòng)態(tài)求極值。其中「動(dòng)態(tài)」和「極值」二者缺一不可。求極值比較好理解無(wú)非是求最大值或最小值而「動(dòng)態(tài)」卻不然。比如求一個(gè)數(shù)組第 k 小的數(shù)這是動(dòng)態(tài)嗎這其實(shí)完全看你怎么理解而在本專題語(yǔ)境下這種情況就是動(dòng)態(tài)的。為什么是動(dòng)態(tài)的可以這樣想由于堆只能求極值比如只能求最小值不能直接求第 k 小的值那是不是可以先求最小的值然后將其出隊(duì)對(duì)應(yīng)上面例子的叫號(hào)再繼續(xù)求最小的值此時(shí)求出的就是第 2 小了如果要求第 k 小就如此反復(fù) k 次。在這個(gè)過(guò)程中數(shù)據(jù)是動(dòng)態(tài)變化的對(duì)應(yīng)的就是堆的大小在變化。下面通過(guò)幾個(gè)例子來(lái)說(shuō)明。例一1046. 最后一塊石頭的重量題目描述有一堆石頭每塊石頭的重量都是正整數(shù)。 每一回合從中選出兩塊 最重的 石頭然后將它們一起粉碎。假設(shè)石頭的重量分別為 x 和 y且 x y。那么粉碎的可能結(jié)果如下 如果 x y那么兩塊石頭都會(huì)被完全粉碎 如果 x ! y那么重量為 x 的石頭將會(huì)完全粉碎而重量為 y 的石頭新重量為 y-x。 最后最多只會(huì)剩下一塊石頭。返回此石頭的重量。如果沒(méi)有石頭剩下就返回 0。 示例 輸入[2,7,4,1,8,1] 輸出1 解釋 先選出 7 和 8得到 1所以數(shù)組轉(zhuǎn)換為 [2,4,1,1,1] 再選出 2 和 4得到 2所以數(shù)組轉(zhuǎn)換為 [2,1,1,1] 接著是 2 和 1得到 1所以數(shù)組轉(zhuǎn)換為 [1,1,1] 最后選出 1 和 1得到 0最終數(shù)組轉(zhuǎn)換為 [1]這就是最后剩下那塊石頭的重量。 提示 1 stones.length 30 1 stones[i] 1000思路題目比較簡(jiǎn)單直接模擬即可。需要注意的是每次選擇兩個(gè)最重的石頭粉碎之后最重的石頭的重量便發(fā)生了變化這會(huì)影響下次取最重的石頭——簡(jiǎn)單來(lái)說(shuō)就是最重的石頭在模擬過(guò)程中是動(dòng)態(tài)變化的。這種動(dòng)態(tài)取極值的場(chǎng)景使用堆就非常適合。當(dāng)然看這個(gè)數(shù)據(jù)范圍1 stones.length 30 且 1 stones[i] 1000使用計(jì)數(shù)的方式應(yīng)該也是可以的。代碼Java大頂堆import java.util.PriorityQueue; public class Solution { public int lastStoneWeight(int[] stones) { int n stones.length; PriorityQueueInteger maxHeap new PriorityQueue(n, (a, b) - b - a); for (int stone : stones) { maxHeap.add(stone); } while (maxHeap.size() 2) { Integer head1 maxHeap.poll(); Integer head2 maxHeap.poll(); if (head1.equals(head2)) { continue; } maxHeap.offer(head1 - head2); } if (maxHeap.isEmpty()) { return 0; } return maxHeap.poll(); } }例二313. 超級(jí)丑數(shù)題目描述編寫(xiě)一段程序來(lái)查找第 n 個(gè)超級(jí)丑數(shù)。 超級(jí)丑數(shù)是指其所有質(zhì)因數(shù)都是長(zhǎng)度為 k 的質(zhì)數(shù)列表 primes 中的正整數(shù)。 示例: 輸入: n 12, primes [2,7,13,19] 輸出: 32 解釋: 給定長(zhǎng)度為 4 的質(zhì)數(shù)列表 primes [2,7,13,19]前 12 個(gè)超級(jí)丑數(shù)序列為[1,2,4,7,8,13,14,16,19,26,28,32] 。 說(shuō)明: 1 是任何給定 primes 的超級(jí)丑數(shù)。 給定 primes 中的數(shù)字以升序排列。 0 k ≤ 100, 0 n ≤ 10^6, 0 primes[i] 1000 。 第 n 個(gè)超級(jí)丑數(shù)確保在 32 位有符整數(shù)范圍內(nèi)。思路這道題看似和動(dòng)態(tài)求極值沒(méi)關(guān)系其實(shí)不然。我們可以預(yù)先生成足夠多的丑數(shù)比如從小到大生成 $N$ 個(gè)然后直接取第 $N$ 個(gè)——但題目數(shù)據(jù)范圍0 n ≤ 10^6預(yù)生成大小為 $10^6$ 的數(shù)組時(shí)間和空間浪費(fèi)都很嚴(yán)重而且如何高效生成也是個(gè)問(wèn)題。通過(guò)丑數(shù)的定義超級(jí)丑數(shù)一定可以寫(xiě)成如下形式if primes [a,b,c,....] then f(ugly) a * x1 * b * x2 * c * x3 ... 其中 x1x2x3 均為正整數(shù)。不妨先將問(wèn)題簡(jiǎn)化考慮題目給的例子[2,7,13,19]可以用四個(gè)指針來(lái)處理直接看代碼public class Solution { public int solve(int n) { int ans[]new int[n5]; ans[0]1; int p10,p20,p30,p40; for(int i1;in;i){ ans[i]Math.min(ans[p1]*2,Math.min(ans[p2]*7,Math.min(ans[p3]*13,ans[p4]*19))); if(ans[i]ans[p1]*2) p1; if(ans[i]ans[p2]*7) p2; if(ans[i]ans[p3]*13) p3; if(ans[i]ans[p3]*19) p4; } return ans[n-1]; } }這個(gè)技巧可以稱之為多路歸并后文「三個(gè)技巧」小節(jié)會(huì)再次用堆來(lái)優(yōu)化它。由于指針是動(dòng)態(tài)的、且指針數(shù)量與primes數(shù)組長(zhǎng)度一致這題也可以看作一個(gè)狀態(tài)機(jī)用記憶化遞歸或動(dòng)態(tài)規(guī)劃解決而這里介紹一種堆的解法相比于動(dòng)態(tài)規(guī)劃個(gè)人認(rèn)為更簡(jiǎn)單、更符合直覺(jué)。實(shí)際上我們可以動(dòng)態(tài)維護(hù)一個(gè)當(dāng)前最小的超級(jí)丑數(shù)找到第一個(gè)將其移除再找下一個(gè)當(dāng)前最小的超級(jí)丑數(shù)也就是全局第二小的超級(jí)丑數(shù)。這樣經(jīng)過(guò) n 輪就得到了第 n 小的超級(jí)丑數(shù)。這種動(dòng)態(tài)維護(hù)極值的場(chǎng)景正是堆的用武之地。以題目給的例子[2,7,13,19]來(lái)說(shuō)將[2,7,13,19]依次入堆出堆一個(gè)數(shù)字也就是 2這時(shí)取到了第一個(gè)超級(jí)丑數(shù)接著將 2 和[2,7,13,19]的乘積也就是[4,14,26,38]依次入堆如此反復(fù)直到取到第 n 個(gè)超級(jí)丑數(shù)。上述正確性是毋庸置疑的每次堆都可以取到最小的每次也會(huì)將最小的從堆中移除因此取 n 次自然就是第 n 小的超級(jí)丑數(shù)。堆的解法唯一需要注意的是去重比如2 * 13 26而13 * 2也是 26不能將 26 入堆兩次。解決方法也很簡(jiǎn)單要么使用哈希表記錄全部已經(jīng)取出的數(shù)對(duì)已經(jīng)取出的數(shù)字不再取另一種方法是記錄上一次取出的數(shù)由于取出的數(shù)字是按照數(shù)字大小不嚴(yán)格遞增的只需要拿上次取出的數(shù)和本次取出的數(shù)比較一下即可。代碼Javaclass Solution { public int nthSuperUglyNumber(int n, int[] primes) { PriorityQueueLong queuenew PriorityQueue(); int count 0; long ans 1; queue.add(ans); while (count n) { ansqueue.poll(); while (!queue.isEmpty() ans queue.peek()) { queue.poll(); } count; for (int i 0; i primes.length ; i) { queue.offer(ans * primes[i]); } } return (int)ans; } }ans初始化為 1 的作用相當(dāng)于虛擬頭僅僅起到了簡(jiǎn)化操作的作用。小結(jié)堆的中心就一個(gè)動(dòng)態(tài)求極值。求極值無(wú)非是最大值或最小值求最大值用大頂堆求最小值用小頂堆。而實(shí)際上如果沒(méi)有「動(dòng)態(tài)」兩個(gè)字很多情況下沒(méi)有必要使用堆——比如可以一次遍歷找出最大值。難點(diǎn)恰恰在于「動(dòng)態(tài)」這個(gè)點(diǎn)不容易看出來(lái)這需要你先對(duì)問(wèn)題進(jìn)行分析分析出這道題其實(shí)就是動(dòng)態(tài)求極值那么使用堆來(lái)優(yōu)化就應(yīng)被想到。類似的例子還有很多后文「三個(gè)技巧」會(huì)做更多講解。倉(cāng)庫(kù)中也有大量同類題解可供對(duì)照練習(xí)例如 295. 數(shù)據(jù)流的中位數(shù)、215. 數(shù)組中的第 K 個(gè)最大元素、378. 有序矩陣中第 K 小的元素。兩種實(shí)現(xiàn)跳表與二叉堆上面簡(jiǎn)單提到了堆的幾種實(shí)現(xiàn)。這里介紹兩種常見(jiàn)的實(shí)現(xiàn)一種是基于鏈表的實(shí)現(xiàn)——跳表另一種是基于數(shù)組的實(shí)現(xiàn)——二叉堆。使用跳表的實(shí)現(xiàn)如果算法沒(méi)有經(jīng)過(guò)精雕細(xì)琢性能會(huì)不太穩(wěn)定且在數(shù)據(jù)量大的情況下內(nèi)存占用會(huì)明顯增加。因此本專題僅詳細(xì)講述二叉堆的實(shí)現(xiàn)對(duì)于跳表實(shí)現(xiàn)僅講述基本原理。跳表以空間換時(shí)間的有序鏈表跳表也是一種數(shù)據(jù)結(jié)構(gòu)在面試中出現(xiàn)的頻率不大但在工業(yè)中經(jīng)常被用到。其設(shè)計(jì)思路值得學(xué)習(xí)比如空間換時(shí)間的思想、效率的取舍問(wèn)題等。前面提到應(yīng)付插隊(duì)問(wèn)題是設(shè)計(jì)堆時(shí)應(yīng)該考慮的首要問(wèn)題。堆的跳表實(shí)現(xiàn)是如何解決的呢我們知道不借助額外空間的情況下在鏈表中查找一個(gè)值需要按順序一個(gè)個(gè)查找時(shí)間復(fù)雜度為 $O(N)$其中 $N$ 為鏈表長(zhǎng)度。當(dāng)鏈表長(zhǎng)度很大時(shí)這種時(shí)間很難接受。一種常見(jiàn)的優(yōu)化方式是建立哈希表將所有節(jié)點(diǎn)都放到哈希表中以空間換時(shí)間將查找復(fù)雜度降到 $O(1)$但空間復(fù)雜度為 $O(N)$。不過(guò)為了防止鏈表出現(xiàn)重復(fù)節(jié)點(diǎn)需要先序列化節(jié)點(diǎn)再建立哈希表空間占用會(huì)更高更重要的是哈希表只能根據(jù) key 獲取內(nèi)容不能解決查找極值的問(wèn)題。為了解決上面的問(wèn)題跳表應(yīng)運(yùn)而生。做法是從鏈表中每?jī)蓚€(gè)元素抽出來(lái)加一級(jí)索引一級(jí)索引指向原始鏈表通過(guò)一級(jí)索引節(jié)點(diǎn)的down指針可以找到原始鏈表的對(duì)應(yīng)節(jié)點(diǎn)。注意這個(gè)算法要求鏈表是有序的。例如查找 10先在一級(jí)跳表中搜索到 7發(fā)現(xiàn)下一個(gè) 18 大于 10即要找的 10 在兩者之間然后通過(guò)down指針回到原始鏈表通過(guò)原始鏈表的next指針找到 10。這個(gè)例子看不出性能提升但如果元素繼續(xù)增多、繼續(xù)增加索引層數(shù)二級(jí)、三級(jí)……索引使鏈表能夠?qū)崿F(xiàn)二分查找就能獲得更好的效率當(dāng)然也需付出額外空間的代價(jià)?？梢园烟硇蜗蟮叵胂鬄橥嬗螒虻拇鏅n一個(gè)游戲有 10 關(guān)想玩第 5 關(guān)的某個(gè)地方可以直接從第 5 關(guān)開(kāi)始甚至可以設(shè)置很多存檔直接選擇離目標(biāo)更近的存檔——這就相當(dāng)于跳表的二級(jí)索引。跳表的時(shí)間復(fù)雜度和空間復(fù)雜度由于時(shí)間復(fù)雜度 索引的高度 × 平均每層索引遍歷元素的個(gè)數(shù)高度大概為 $\log n$且每層遍歷的元素是常數(shù)因此時(shí)間復(fù)雜度為 $O(\log n)$?？臻g復(fù)雜度等同于索引節(jié)點(diǎn)的個(gè)數(shù)以每?jī)蓚€(gè)節(jié)點(diǎn)建立一個(gè)索引為例大約是 $n/2 n/4 n/8 … 8 4 2$因此空間復(fù)雜度是 $O(n)$當(dāng)然每三個(gè)節(jié)點(diǎn)建立一個(gè)索引會(huì)更省空間但復(fù)雜度不變。理解了上面的內(nèi)容使用跳表實(shí)現(xiàn)堆就不難了入堆根據(jù)索引插到鏈表中并更新索引可選出堆刪除頭部或尾部并更新索引可選。如果想檢測(cè)自己的跳表實(shí)現(xiàn)是否有問(wèn)題可以去 LeetCode 的 1206. 設(shè)計(jì)跳表 檢測(cè)。二叉堆一顆特殊的完全二叉樹(shù)二叉堆的實(shí)現(xiàn)本專題僅講解最核心的兩個(gè)操作heappop出堆和heappush入堆。實(shí)現(xiàn)之后的使用效果大概是這樣h min_heap() h.build_heap([5, 6, 2, 3]) h.heappush(1) h.heappop() # 1 h.heappop() # 2 h.heappush(1) h.heappop() # 1 h.heappop() # 3基本原理本質(zhì)上來(lái)說(shuō)二叉堆就是一顆特殊的完全二叉樹(shù)它的特殊性只體現(xiàn)在一點(diǎn)父節(jié)點(diǎn)的權(quán)值不大于兒子的權(quán)值小頂堆。這一點(diǎn)需要牢記一切的一切都源于這句話。由于父節(jié)點(diǎn)的權(quán)值不大于兒子的權(quán)值很自然能推導(dǎo)出樹(shù)的根節(jié)點(diǎn)就是最小值這就起到了堆「取極值」的作用。那么「動(dòng)態(tài)性」呢二叉堆是怎么做到的出堆下沉如果將樹(shù)的根節(jié)點(diǎn)出堆根節(jié)點(diǎn)就空缺了應(yīng)該讓第二小的頂替上去。如果僅僅是刪除一個(gè)堆就會(huì)變成兩個(gè)堆問(wèn)題變復(fù)雜了。一個(gè)常見(jiàn)的操作是把根結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)交換。但新的根結(jié)點(diǎn)可能不滿足堆性質(zhì)父節(jié)點(diǎn)的權(quán)值不大于兒子的權(quán)值此時(shí)只需要將新的根節(jié)點(diǎn)下沉到正確位置即可。這里的「正確位置」指的依然是那句堆性質(zhì)如果不滿足就繼續(xù)下沉直到滿足。需要注意的是根節(jié)點(diǎn)往下下沉?xí)r有兩個(gè)方向可供選擇下沉到左子節(jié)點(diǎn)還是右子節(jié)點(diǎn)以小頂堆來(lái)說(shuō)答案應(yīng)該是下沉到較小的子節(jié)點(diǎn)處否則會(huì)錯(cuò)失正確答案。以下面的堆為例如果下沉到右子節(jié)點(diǎn) 4就無(wú)法得到正確的堆頂 3因此需要下沉到左子節(jié)點(diǎn)。有的同學(xué)可能有疑問(wèn)彈出根節(jié)點(diǎn)前堆滿足性質(zhì)彈出之后經(jīng)過(guò)下沉操作一定還滿足嗎答案是肯定的。由于最后的葉子節(jié)點(diǎn)被提到了根節(jié)點(diǎn)它最終在哪是不確定的但經(jīng)過(guò)上面的操作可以看出其下沉路徑上的節(jié)點(diǎn)一定都滿足堆的性質(zhì)不在下沉路徑上的節(jié)點(diǎn)都保持了堆之前的相對(duì)關(guān)系因此也滿足堆的性質(zhì)。因此彈出根節(jié)點(diǎn)后經(jīng)過(guò)下沉操作一定仍然滿足堆的性質(zhì)。時(shí)間復(fù)雜度方面可以證明下沉和樹(shù)的高度成正相關(guān)因此時(shí)間復(fù)雜度為 $O(h)$其中 $h$ 為樹(shù)高而由于二叉堆是完全二叉樹(shù)樹(shù)高大約是 $\log N$其中 $N$ 為樹(shù)中的節(jié)點(diǎn)個(gè)數(shù)。入堆上浮入堆和出堆類似可以直接往樹(shù)的最后插入一個(gè)節(jié)點(diǎn)。之所以這么做其中一個(gè)原因是時(shí)間復(fù)雜度更低——我們是用數(shù)組進(jìn)行模擬的而在數(shù)組尾部添加元素的時(shí)間復(fù)雜度為 $O(1)$。但同樣的這樣的操作可能破壞堆的性質(zhì)。這次不滿足堆的節(jié)點(diǎn)是剛插入的尾部節(jié)點(diǎn)因此不能進(jìn)行下沉操作了需要執(zhí)行上浮操作葉子節(jié)點(diǎn)只能上浮根節(jié)點(diǎn)只能下沉其他節(jié)點(diǎn)既可以下沉又可以上浮。和上面基本類似如果不滿足堆的性質(zhì)將其和父節(jié)點(diǎn)交換上浮繼續(xù)這個(gè)過(guò)程直到滿足。經(jīng)過(guò)這樣的操作其仍是一個(gè)滿足堆性質(zhì)的堆證明過(guò)程與下沉類似不再贅述。需要注意的是由于上浮只需要拿當(dāng)前節(jié)點(diǎn)和父節(jié)點(diǎn)進(jìn)行比對(duì)省去了判斷左右子節(jié)點(diǎn)哪個(gè)更小的過(guò)程因此更加簡(jiǎn)單。數(shù)組表示與核心代碼對(duì)于完全二叉樹(shù)來(lái)說(shuō)使用數(shù)組實(shí)現(xiàn)非常方便因?yàn)榇嬖谌缦伦鴺?biāo)關(guān)系要求數(shù)組從 1 開(kāi)始存儲(chǔ)數(shù)據(jù)這是一種業(yè)界習(xí)慣如果節(jié)點(diǎn)在數(shù)組中的下標(biāo)為i那么其左子節(jié)點(diǎn)下標(biāo)為 $2 \times i$右子節(jié)點(diǎn)為 $2 \times i 1$如果節(jié)點(diǎn)在數(shù)組中的下標(biāo)為i那么父節(jié)點(diǎn)下標(biāo)為i // 2地板除。從 1 開(kāi)始存儲(chǔ)的另外一個(gè)好處是可以將索引 0 的位置空出來(lái)存儲(chǔ)諸如堆大小的信息這是一些大學(xué)教材里的做法。有了上浮/下沉過(guò)程再配合父子節(jié)點(diǎn)坐標(biāo)關(guān)系代碼就呼之欲出了。先看核心的上浮與下沉偽代碼// x 是要上浮的元素從樹(shù)的底部開(kāi)始上浮 private void shift_up(int x) { while (x 1 h[x] h[x / 2]) { // swap 就是交換數(shù)組兩個(gè)位置的值 swap(h[x], h[x / 2]); x / 2; } } // x 是要下沉的元素從樹(shù)的頂部開(kāi)始下沉 private void shift_down(int x) { while (x * 2 n) { // minChild 是獲取更小的子節(jié)點(diǎn)的索引并返回 mc minChild(x); if (h[mc] h[x]) break; swap(h[x], h[mc]); x mc; } }以 Java 為例的完整實(shí)現(xiàn)數(shù)組下標(biāo)從 1 開(kāi)始import java.util.Arrays; import java.util.Comparator; /** * 用完全二叉樹(shù)來(lái)構(gòu)建 堆 * 前置條件 起點(diǎn)為 1 * 那么 子節(jié)點(diǎn)為 i 1 和 i1 1 * 核心方法為 * shiftdown 交換下沉 * shiftup 交換上浮 * build 構(gòu)建堆 */ public class Heap { int size 0; int queue[]; public Heap(int initialCapacity) { if (initialCapacity 1) throw new IllegalArgumentException(); this.queue new int[initialCapacity]; } public Heap(int[] arr) { size arr.length; queue new int[arr.length 1]; int i 1; for (int val : arr) { queue[i] val; } } public void shiftDown(int i) { int temp queue[i]; while ((i 1) size) { int child i 1; // child!size 判斷當(dāng)前元素是否包含右節(jié)點(diǎn) if (child ! size queue[child 1] queue[child]) { child; } if (temp queue[child]) { queue[i] queue[child]; i child; } else { break; } } queue[i] temp; } public void shiftUp(int i) { int temp queue[i]; while ((i 1) 0) { if (temp queue[i 1]) { queue[i] queue[i 1]; i 1; } else { break; } } queue[i] temp; } public int peek() { int res queue[1]; return res; } public int pop() { int res queue[1]; queue[1] queue[size--]; shiftDown(1); return res; } public void push(int val) { if (size queue.length - 1) { queue Arrays.copyOf(queue, size 11); } queue[size] val; shiftUp(size); } public void buildHeap() { for (int i size 1; i 0; i--) { shiftDown(i); } } public static void main(String[] args) { int arr[] new int[]{2,7,4,1,8,1}; Heap heap new Heap(arr); heap.buildHeap(); System.out.println(heap.peek()); heap.push(5); while (heap.size 0) { int num heap.pop(); System.out.printf(num ); } } }小結(jié)堆的實(shí)現(xiàn)有很多基于鏈表的跳表、基于數(shù)組的二叉堆、基于紅黑樹(shù)的實(shí)現(xiàn)等。本專題詳細(xì)講述了二叉堆的實(shí)現(xiàn)不僅因?yàn)樗鼘?shí)現(xiàn)簡(jiǎn)單而且它在很多情況下表現(xiàn)都不錯(cuò)推薦重點(diǎn)掌握二叉堆實(shí)現(xiàn)。對(duì)于二叉堆的實(shí)現(xiàn)核心點(diǎn)就一點(diǎn)始終維護(hù)堆的性質(zhì)不變即「父節(jié)點(diǎn)的權(quán)值不大于兒子的權(quán)值小頂堆」。為了達(dá)到這個(gè)目的需要在入堆和出堆時(shí)使用上浮和下沉操作并恰當(dāng)?shù)赝瓿稍亟粨Q——具體來(lái)說(shuō)上浮過(guò)程與比它大的父節(jié)點(diǎn)進(jìn)行交換下沉過(guò)程與兩個(gè)子節(jié)點(diǎn)中較小的進(jìn)行交換前提是它有子節(jié)點(diǎn)且子節(jié)點(diǎn)比它小。關(guān)于堆化buildHeap這里沒(méi)有做詳細(xì)分析但理解了入堆操作后這其實(shí)很容易——堆化本身就是一個(gè)不斷入堆的過(guò)程只不過(guò)將時(shí)間上離散的操作變成了一次性操作而已。三個(gè)技巧與四大應(yīng)用進(jìn)階解題套路本專題分為兩個(gè)部分第一部分即本文主體講清了「一個(gè)中心」與「兩種實(shí)現(xiàn)」第二部分對(duì)應(yīng) thinkings/heap-2.en.md專門講三個(gè)技巧與四大應(yīng)用這是專門教你怎么解題的掌握了它們力扣中大多數(shù)堆的題目都不在話下。三個(gè)技巧多路歸并上面講超級(jí)丑數(shù)時(shí)其實(shí)已經(jīng)提到了只是沒(méi)有給它命名。多路體現(xiàn)在有多個(gè)候選路代碼中用多個(gè)指針表示歸并體現(xiàn)在結(jié)果可能是多條候選路中的最長(zhǎng)、最短或第 k 個(gè)等需要比較多條路的結(jié)果并根據(jù)題意取舍。倉(cāng)庫(kù)中的 23. 合并 K 個(gè)排序鏈表 正是這一技巧的經(jīng)典載體把 k 個(gè)有序鏈表的頭結(jié)點(diǎn)放入小頂堆每次彈出最小節(jié)點(diǎn)并推入其后繼即可在 $O(N\log k)$ 時(shí)間內(nèi)完成合并。固定堆把堆的大小固定為 k 不變代碼上通過(guò)「推入一個(gè)的同時(shí)彈出一個(gè)」來(lái)實(shí)現(xiàn)初始時(shí)逐個(gè)推入使堆大小達(dá)到 k嚴(yán)格來(lái)說(shuō)是維護(hù)堆的大小不大于 k。固定大小為 k 的大頂堆可以快速求第 k 小的數(shù)堆內(nèi)維護(hù)的是全局最小的 k 個(gè)數(shù)堆頂是其中最大的即第 k 小反之固定大小為 k 的小頂堆可以快速求第 k 大的數(shù)。經(jīng)典應(yīng)用如 295. 數(shù)據(jù)流的中位數(shù)維護(hù)兩個(gè)固定堆——大頂堆放較小的 $(n1)/2$ 個(gè)數(shù)、小頂堆放較大的 $n - (n1)/2$ 個(gè)數(shù)兩堆堆頂即為中位數(shù)addNum與findMedian均可在 $O(\log n)$ / $O(1)$ 內(nèi)完成。倉(cāng)庫(kù)題解 295.find-median-from-data-stream.md 對(duì)該題有完整的雙堆推導(dǎo)與代碼。事后小諸葛指先按某種順序處理數(shù)據(jù)、事后再用堆做修正的技巧具體內(nèi)容詳見(jiàn)續(xù)篇 thinkings/heap-2.en.md。四大應(yīng)用topK求第 k 大/第 k 小、最小的 k 個(gè)數(shù)等是固定堆技巧的直接應(yīng)用倉(cāng)庫(kù)中的 215. 數(shù)組中的第 K 個(gè)最大元素 與 378. 有序矩陣中第 K 小的元素 都是典型例題。帶權(quán)最短距離即 dijkstra 算法用優(yōu)先隊(duì)列做 BFS 處理帶權(quán)圖最短路徑這正是前面「隊(duì)列 VS 優(yōu)先隊(duì)列」一節(jié)強(qiáng)調(diào)過(guò)的場(chǎng)景。因子分解如超級(jí)丑數(shù)、丑數(shù)相關(guān)題解 等通過(guò)堆動(dòng)態(tài)維護(hù)最小因子組合生成序列。堆排序建堆后不斷pop堆頂即可得到有序序列——上文的Heap.main演示的正是這個(gè)過(guò)程輸出1 2 4 5 7 8。倉(cāng)庫(kù)配套資源導(dǎo)航本專題在倉(cāng)庫(kù)中有完整的中英文文檔與配套題解可按需深入閱讀專題第一講thinkings/heap.en.md英文版與 thinkings/heap.md中文版覆蓋「一個(gè)中心、兩種實(shí)現(xiàn)」即本文內(nèi)容專題第二講thinkings/heap-2.en.md 與 thinkings/heap-2.md覆蓋「三個(gè)技巧、四大應(yīng)用」的詳細(xì)題解如 295、857、1439 等 hard 題目倉(cāng)庫(kù)配套題解295.find-median-from-data-stream.md雙堆求中位數(shù)、23.merge-k-sorted-lists.md多路歸并合并 K 個(gè)鏈表、215.kth-largest-element-in-an-array.md 與 378.kth-smallest-element-in-a-sorted-matrix.mdtopK 類、513.find-bottom-left-tree-value.md優(yōu)先隊(duì)列實(shí)現(xiàn) BFS 的演示相關(guān)思維導(dǎo)圖與圖示可參考 assets/thinkings/min-heap.png小頂堆結(jié)構(gòu)示意圖、assets/thinkings/max-heap.svg大頂堆結(jié)構(gòu)示意圖?？偨Y(jié)堆專題看似難困難題占比近半但解題核心其實(shí)高度收斂識(shí)別場(chǎng)景凡是「數(shù)據(jù)在動(dòng)態(tài)變化、需要反復(fù)取極值」的問(wèn)題優(yōu)先想到堆理解本質(zhì)堆是一顆特殊的完全二叉樹(shù)父節(jié)點(diǎn)權(quán)值不大于子節(jié)點(diǎn)根節(jié)點(diǎn)即極值入堆/出堆通過(guò)上浮/下沉維持堆性質(zhì)復(fù)雜度均為 $O(\log N)$套用套路多路歸并、固定堆、事后小諸葛三個(gè)技巧覆蓋 topK、帶權(quán)最短距離、因子分解、堆排序四大應(yīng)用幾乎可以解決力扣上絕大多數(shù)與堆相關(guān)的題目。把「一個(gè)中心、兩種實(shí)現(xiàn)、三個(gè)技巧、四大應(yīng)用」這條主線吃透再配合倉(cāng)庫(kù)中的中英文專題文檔與逐題題解反復(fù)演練堆就不再是攔路虎。【免費(fèi)下載鏈接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode題解記錄自己的leetcode解題之路。)項(xiàng)目地址: https://gitcode.com/gh_mirrors/le/leetcode創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考 LeetCode 堆（優(yōu)先隊(duì)列）專題精講：一個(gè)中心、兩種實(shí)現(xiàn)、三個(gè)技巧與四大應(yīng)用
LeetCode 堆優(yōu)先隊(duì)列專題精講一個(gè)中心、兩種實(shí)現(xiàn)、三個(gè)技巧與四大應(yīng)用【免費(fèi)下載鏈接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode題解記錄自己的leetcode解題之路。)項(xiàng)目地址: https://gitcode.com/gh_mirrors/le/leetcode本文源自 thinkings/heap.en.md堆專題第一講及其續(xù)篇 thinkings/heap-2.en.md堆專題第二講三個(gè)技巧。它系統(tǒng)梳理了「堆/優(yōu)先隊(duì)列」這一數(shù)據(jù)結(jié)構(gòu)的適用場(chǎng)景、核心原理、實(shí)現(xiàn)方式與解題套路是刷 LeetCode 堆類題目官方標(biāo)簽約 42 道困難度接近 50%之前值得先讀的專題總綱。讀完本文你將掌握用「動(dòng)態(tài)求極值」這一中心思想識(shí)別堆題、用跳表與二叉堆兩種視角理解堆的底層原理、以及多路歸并、固定堆等直接可用的解題模板。說(shuō)明本文中「堆」與「優(yōu)先隊(duì)列」不做區(qū)分二者可視為同一事物除非特別說(shuō)明本文所說(shuō)的堆均指小頂堆即堆頂為最小值父節(jié)點(diǎn)權(quán)值不大于子節(jié)點(diǎn)權(quán)值。一點(diǎn)絮叨為什么值得專門開(kāi)一個(gè)堆專題堆在 LeetCode 中被單獨(dú)打上了標(biāo)簽。從官方難度標(biāo)簽來(lái)看堆的題目一共 42 道其中困難題占比將近 50%作為對(duì)比樹(shù)專題的困難度只有不到 10%從通過(guò)率來(lái)看一半以上的堆題目平均通過(guò)率在 50% 以下而樹(shù)專題通過(guò)率在 50% 以下的只有不到三分之一。因此堆確實(shí)是一個(gè)難度不低的專題。為此本專題的核心方法論被提煉為一句話口訣一個(gè)中心兩種實(shí)現(xiàn)三個(gè)技巧四大應(yīng)用。一個(gè)中心動(dòng)態(tài)求極值。兩種實(shí)現(xiàn)跳表實(shí)現(xiàn)與二叉堆實(shí)現(xiàn)。三個(gè)技巧多路歸并、固定堆、事后小諸葛。四大應(yīng)用topK、帶權(quán)最短距離、因子分解、堆排序。下文將沿著這條主線逐一展開(kāi)既講實(shí)現(xiàn)與原理更講問(wèn)題背后的背景、套路與模板。堆的使用場(chǎng)景從「掛號(hào)系統(tǒng)」說(shuō)起堆是一種數(shù)據(jù)結(jié)構(gòu)而數(shù)據(jù)結(jié)構(gòu)是為算法服務(wù)的。學(xué)習(xí)堆要解決的第一個(gè)問(wèn)題是堆到底解決什么問(wèn)題、適用于什么場(chǎng)景這里給出的學(xué)習(xí)建議是先不要糾結(jié)堆怎么實(shí)現(xiàn)的先了解堆解決了什么問(wèn)題。當(dāng)你理解了使用背景之后先當(dāng)一個(gè)「調(diào)包俠」直接用現(xiàn)成的堆 API 解決問(wèn)題等理解得差不多了再回頭去看堆的原理和實(shí)現(xiàn)。為了說(shuō)明堆的使用場(chǎng)景這里虛構(gòu)了一個(gè)場(chǎng)景——排隊(duì)掛號(hào)系統(tǒng)。下面這個(gè)例子很重要后面會(huì)反復(fù)與它對(duì)比。問(wèn)題描述假如你是一個(gè)排隊(duì)掛號(hào)系統(tǒng)的技術(shù)負(fù)責(zé)人。該系統(tǒng)需要給每一個(gè)前來(lái)排隊(duì)的人發(fā)放一個(gè)排隊(duì)碼入隊(duì)并根據(jù)先來(lái)后到的原則進(jìn)行叫號(hào)出隊(duì)。除此之外系統(tǒng)還區(qū)分了幾種客戶類型普通客戶、VIP 客戶、至尊 VIP 客戶。由此衍生出兩個(gè)設(shè)計(jì)問(wèn)題問(wèn)題一如果不同的客戶使用不同的窗口VIP 客戶由專家醫(yī)生服務(wù)普通客戶由普通醫(yī)生服務(wù)系統(tǒng)該如何設(shè)計(jì)實(shí)現(xiàn)問(wèn)題二如果不同的客戶都使用同一個(gè)窗口服務(wù)內(nèi)容相同但優(yōu)先級(jí)不同比如同時(shí)來(lái)掛號(hào)的 VIP 客戶優(yōu)先級(jí)高于普通客戶系統(tǒng)又該如何設(shè)計(jì)實(shí)現(xiàn)初步的解決方案如果不同的客戶使用不同的窗口那么可以設(shè)計(jì)三個(gè)隊(duì)列分別存放正在排隊(duì)的三種人。這種設(shè)計(jì)滿足要求也足夠簡(jiǎn)單。如果只有一個(gè)窗口所有病人需要使用同一個(gè)隊(duì)列且相同客戶類型內(nèi)部按照先到先服務(wù)原則但不同客戶類型之間允許插隊(duì)。簡(jiǎn)單起見(jiàn)引入虛擬時(shí)間的概念普通客戶的虛擬時(shí)間就是真實(shí)時(shí)間VIP 客戶的虛擬時(shí)間 實(shí)際到達(dá)時(shí)間 ? 1 小時(shí)例如 14:00 到達(dá)視為 13:00 到達(dá)至尊 VIP 客戶的虛擬時(shí)間 實(shí)際到達(dá)時(shí)間 ? 2 小時(shí)例如 14:00 到達(dá)視為 12:00 到達(dá)。這樣系統(tǒng)只需要按照「虛擬到達(dá)時(shí)間」進(jìn)行先到先服務(wù)即可——繼續(xù)使用三個(gè)隊(duì)列的方式只不過(guò)隊(duì)列里存儲(chǔ)的不是真實(shí)時(shí)間而是虛擬時(shí)間每次叫號(hào)時(shí)比較虛擬時(shí)間虛擬時(shí)間較小的先服務(wù)。不難看出隊(duì)列內(nèi)部的時(shí)間都是有序的。而這里的虛擬時(shí)間其實(shí)就是優(yōu)先隊(duì)列中的「優(yōu)先權(quán)重」——虛擬時(shí)間越小權(quán)重越大。可以插隊(duì)怎么辦上述算法能很好地完成需求但新的產(chǎn)品需求出現(xiàn)了別的門診的病人轉(zhuǎn)院到本診所按照他之前的排隊(duì)信息計(jì)算例如 12:00 在別的院掛的號(hào)轉(zhuǎn)到本院仍按 12:00 掛號(hào)算被叫到號(hào)三分鐘沒(méi)有應(yīng)答的作廢但如果病人重新回來(lái)則按「當(dāng)前時(shí)間 ? 1 小時(shí)」作為虛擬時(shí)間重新排隊(duì)。這樣就出現(xiàn)了「插隊(duì)」的情況。一個(gè)簡(jiǎn)單的做法是將其插入到正確位置并重新調(diào)整后面所有人的排隊(duì)位置。如果隊(duì)列用數(shù)組實(shí)現(xiàn)插隊(duì)過(guò)程的時(shí)間復(fù)雜度為 $O(N)$其中 $N$ 為被插隊(duì)的隊(duì)伍長(zhǎng)度隊(duì)伍很長(zhǎng)時(shí)調(diào)整次數(shù)明顯增加。本質(zhì)上我們是在維護(hù)一個(gè)有序列表數(shù)組方式的好處是隨機(jī)訪問(wèn)但這個(gè)需求并不需要該特性用鏈表實(shí)現(xiàn)插入理論上是 $O(1)$但定位插入位置需要遍歷查找復(fù)雜度又退化為 $O(N)$。有沒(méi)有時(shí)間復(fù)雜度更好的做法答案就是本文的主角——優(yōu)先隊(duì)列。有序鏈表的查找可以優(yōu)化由于是有序的可以用跳表加速查找時(shí)間復(fù)雜度可優(yōu)化到 $O(\log N)$。事實(shí)上算法界有很多類似的問(wèn)題例如數(shù)據(jù)庫(kù)索引給有序的列添加索引時(shí)不能每次插入一條數(shù)據(jù)都調(diào)整所有數(shù)據(jù)因此可以用平衡樹(shù)來(lái)實(shí)現(xiàn)每次插入最多調(diào)整 $O(\log N)$ 個(gè)節(jié)點(diǎn)。優(yōu)先隊(duì)列的另外一種實(shí)現(xiàn)——二叉堆正是這個(gè)思想時(shí)間復(fù)雜度同樣可以優(yōu)化到 $O(\log N)$。使用堆解決問(wèn)題堆的兩個(gè)核心 API 是push和pop。先把它想象成一個(gè)黑盒push推入一個(gè)數(shù)據(jù)內(nèi)部怎么組織不用管對(duì)應(yīng)場(chǎng)景中的排隊(duì)和插隊(duì)pop彈出一個(gè)數(shù)據(jù)彈出的數(shù)據(jù)一定是最小的內(nèi)部怎么實(shí)現(xiàn)不用管對(duì)應(yīng)場(chǎng)景中的叫號(hào)。這里的例子是小頂堆如果彈出的數(shù)據(jù)一定是最大的則對(duì)應(yīng)大頂堆的實(shí)現(xiàn)。借助這兩個(gè) API 就能實(shí)現(xiàn)上面的需求Python 的heapq寫(xiě)法如下# 12:00 來(lái)了一個(gè)普通的顧客push heapq.heappush(normal_pq, 12:00) # 12:30 來(lái)了一個(gè)普通顧客push heapq.heappush(normal_pq, 12:30) # 13:00 來(lái)了一個(gè)普通顧客push heapq.heappush(normal_pq, 13:00) # 插隊(duì)push時(shí)間復(fù)雜度可以達(dá)到 O(logN)。如何做到先不管我們先會(huì)用就行。 heapq.heappush(normal_pq, 12:20) # 叫號(hào)pop。12:00 來(lái)的先被叫到。注意這里彈出時(shí)間復(fù)雜度也變成了 O(logN)。 heapq.heappop(normal_pq)小結(jié)上面這個(gè)場(chǎng)景單純使用數(shù)組和鏈表都可以滿足需求但在應(yīng)對(duì)「插隊(duì)」時(shí)表現(xiàn)各異若永遠(yuǎn)維護(hù)一個(gè)有序數(shù)組取極值很容易但插隊(duì)麻煩$O(N)$若永遠(yuǎn)維護(hù)一個(gè)有序鏈表取極值也容易但要想查找足夠快而不是線性掃描就需要借助索引對(duì)應(yīng)優(yōu)先隊(duì)列的跳表實(shí)現(xiàn)若永遠(yuǎn)維護(hù)一棵樹(shù)根節(jié)點(diǎn)即極值$O(1)$ 可取到極值但調(diào)整過(guò)程需要 $O(\log N)$對(duì)應(yīng)優(yōu)先隊(duì)列的二叉堆實(shí)現(xiàn)。一句話總結(jié)堆就是動(dòng)態(tài)幫你求極值的。當(dāng)你需要?jiǎng)討B(tài)求最大或最小值時(shí)就用它。具體怎么實(shí)現(xiàn)、復(fù)雜度如何分析后面再講現(xiàn)在只需記住使用場(chǎng)景、堆如何解決這些問(wèn)題以及堆的 API 即可。隊(duì)列 VS 優(yōu)先隊(duì)列隊(duì)列只是一種特殊的優(yōu)先隊(duì)列在講具體實(shí)現(xiàn)之前有必要回答一個(gè)普遍關(guān)心的問(wèn)題優(yōu)先隊(duì)列是隊(duì)列嗎很多人認(rèn)為隊(duì)列和優(yōu)先隊(duì)列是完全不同的東西。但本專題的觀點(diǎn)不同普通的隊(duì)列也可以看成是一個(gè)特殊的優(yōu)先級(jí)隊(duì)列——隊(duì)列無(wú)非就是以「時(shí)間」這一變量作為優(yōu)先級(jí)的優(yōu)先隊(duì)列時(shí)間越早優(yōu)先級(jí)越高越先出隊(duì)。這與網(wǎng)上大多數(shù)「優(yōu)先級(jí)隊(duì)列和隊(duì)列沒(méi)什么關(guān)系」的說(shuō)法有所區(qū)別。平時(shí)寫(xiě) BFS 時(shí)都會(huì)用到隊(duì)列來(lái)處理節(jié)點(diǎn)的訪問(wèn)順序。那使用優(yōu)先隊(duì)列行不行當(dāng)然可以以 513. 找樹(shù)左下角的值 為例。例題513. 找樹(shù)左下角的值題目描述定一個(gè)二叉樹(shù)在樹(shù)的最后一行找到最左邊的值。 示例 1: 輸入: 2 / \ 1 3 輸出: 1 示例 2: 輸入: 1 / \ 2 3 / / \ 4 5 6 / 7 輸出: 7 注意: 您可以假設(shè)樹(shù)即給定的根節(jié)點(diǎn)不為 NULL。思路可以使用 BFS 做一次層次遍歷并且每一層都從右向左遍歷這樣層次遍歷的最后一個(gè)節(jié)點(diǎn)就是樹(shù)左下角的節(jié)點(diǎn)。常規(guī)做法是使用雙端隊(duì)列普通隊(duì)列實(shí)現(xiàn)利用先進(jìn)先出的原則很方便地實(shí)現(xiàn)層次遍歷。代碼普通隊(duì)列版class Solution: def findBottomLeftValue(self, root: TreeNode) - int: if root is None: return None queue collections.deque([root]) ans None while queue: size len(queue) for _ in range(size): ans node queue.popleft() if node.right: queue.append(node.right) if node.left: queue.append(node.left) return ans.val代碼優(yōu)先隊(duì)列版實(shí)際上也可以使用優(yōu)先隊(duì)列思路和代碼幾乎與上面完全一樣class Solution: def findBottomLeftValue(self, root: TreeNode) - int: if root is None: return None queue [] # 堆存儲(chǔ)三元組(a,b,c)a 表示層級(jí)b 表示節(jié)點(diǎn)編號(hào)以完全二叉樹(shù)的形式編號(hào)空節(jié)點(diǎn)也編號(hào)c 是節(jié)點(diǎn)本身 heapq.heappush(queue, (1, 1, root)) ans None while queue: size len(queue) for _ in range(size): level, i, node heapq.heappop(queue) ans node if node.right: heapq.heappush(queue, (level 1, 2 * i 1, node.right)) if node.left: heapq.heappush(queue, (level 1, 2 * i 2, node.left)) return ans.val小結(jié)所有使用隊(duì)列的地方都可以使用優(yōu)先隊(duì)列來(lái)完成反之卻不一定。那既然優(yōu)先隊(duì)列這么厲害為什么平時(shí)用隊(duì)列的地方?jīng)]人用堆最核心的原因是時(shí)間復(fù)雜度更差上面的例子中本來(lái)入隊(duì)和出隊(duì)都可以在 $O(1)$ 時(shí)間完成而現(xiàn)在入隊(duì)和出隊(duì)的復(fù)雜度都是 $O(\log N)$$N$ 為當(dāng)前隊(duì)列大小。因此在沒(méi)有必要的地方使用堆會(huì)大大提高算法的時(shí)間復(fù)雜度。不過(guò) BFS 真的沒(méi)人用優(yōu)先隊(duì)列實(shí)現(xiàn)嗎當(dāng)然不是比如帶權(quán)圖的最短路徑問(wèn)題用隊(duì)列做 BFS 就需要優(yōu)先隊(duì)列因?yàn)槁窂街g有權(quán)重的差異——這正是優(yōu)先隊(duì)列的設(shè)計(jì)初衷。使用優(yōu)先隊(duì)列的 BFS 最典型的就是dijkstra 算法。這再次印證了那句話隊(duì)列就是一種特殊的優(yōu)先隊(duì)列特殊到權(quán)重就是按照到來(lái)的順序定誰(shuí)先來(lái)誰(shuí)的優(yōu)先級(jí)高在這種特殊情況下不必維護(hù)堆從而獲得更好的時(shí)間復(fù)雜度。一個(gè)中心動(dòng)態(tài)求極值堆的問(wèn)題核心點(diǎn)就一個(gè)動(dòng)態(tài)求極值。其中「動(dòng)態(tài)」和「極值」二者缺一不可。求極值比較好理解無(wú)非是求最大值或最小值而「動(dòng)態(tài)」卻不然。比如求一個(gè)數(shù)組第 k 小的數(shù)這是動(dòng)態(tài)嗎這其實(shí)完全看你怎么理解而在本專題語(yǔ)境下這種情況就是動(dòng)態(tài)的。為什么是動(dòng)態(tài)的可以這樣想由于堆只能求極值比如只能求最小值不能直接求第 k 小的值那是不是可以先求最小的值然后將其出隊(duì)對(duì)應(yīng)上面例子的叫號(hào)再繼續(xù)求最小的值此時(shí)求出的就是第 2 小了如果要求第 k 小就如此反復(fù) k 次。在這個(gè)過(guò)程中數(shù)據(jù)是動(dòng)態(tài)變化的對(duì)應(yīng)的就是堆的大小在變化。下面通過(guò)幾個(gè)例子來(lái)說(shuō)明。例一1046. 最后一塊石頭的重量題目描述有一堆石頭每塊石頭的重量都是正整數(shù)。 每一回合從中選出兩塊 最重的 石頭然后將它們一起粉碎。假設(shè)石頭的重量分別為 x 和 y且 x y。那么粉碎的可能結(jié)果如下 如果 x y那么兩塊石頭都會(huì)被完全粉碎 如果 x ! y那么重量為 x 的石頭將會(huì)完全粉碎而重量為 y 的石頭新重量為 y-x。 最后最多只會(huì)剩下一塊石頭。返回此石頭的重量。如果沒(méi)有石頭剩下就返回 0。 示例 輸入[2,7,4,1,8,1] 輸出1 解釋 先選出 7 和 8得到 1所以數(shù)組轉(zhuǎn)換為 [2,4,1,1,1] 再選出 2 和 4得到 2所以數(shù)組轉(zhuǎn)換為 [2,1,1,1] 接著是 2 和 1得到 1所以數(shù)組轉(zhuǎn)換為 [1,1,1] 最后選出 1 和 1得到 0最終數(shù)組轉(zhuǎn)換為 [1]這就是最后剩下那塊石頭的重量。 提示 1 stones.length 30 1 stones[i] 1000思路題目比較簡(jiǎn)單直接模擬即可。需要注意的是每次選擇兩個(gè)最重的石頭粉碎之后最重的石頭的重量便發(fā)生了變化這會(huì)影響下次取最重的石頭——簡(jiǎn)單來(lái)說(shuō)就是最重的石頭在模擬過(guò)程中是動(dòng)態(tài)變化的。這種動(dòng)態(tài)取極值的場(chǎng)景使用堆就非常適合。當(dāng)然看這個(gè)數(shù)據(jù)范圍1 stones.length 30 且 1 stones[i] 1000使用計(jì)數(shù)的方式應(yīng)該也是可以的。代碼Java大頂堆import java.util.PriorityQueue; public class Solution { public int lastStoneWeight(int[] stones) { int n stones.length; PriorityQueueInteger maxHeap new PriorityQueue(n, (a, b) - b - a); for (int stone : stones) { maxHeap.add(stone); } while (maxHeap.size() 2) { Integer head1 maxHeap.poll(); Integer head2 maxHeap.poll(); if (head1.equals(head2)) { continue; } maxHeap.offer(head1 - head2); } if (maxHeap.isEmpty()) { return 0; } return maxHeap.poll(); } }例二313. 超級(jí)丑數(shù)題目描述編寫(xiě)一段程序來(lái)查找第 n 個(gè)超級(jí)丑數(shù)。 超級(jí)丑數(shù)是指其所有質(zhì)因數(shù)都是長(zhǎng)度為 k 的質(zhì)數(shù)列表 primes 中的正整數(shù)。 示例: 輸入: n 12, primes [2,7,13,19] 輸出: 32 解釋: 給定長(zhǎng)度為 4 的質(zhì)數(shù)列表 primes [2,7,13,19]前 12 個(gè)超級(jí)丑數(shù)序列為[1,2,4,7,8,13,14,16,19,26,28,32] 。 說(shuō)明: 1 是任何給定 primes 的超級(jí)丑數(shù)。 給定 primes 中的數(shù)字以升序排列。 0 k ≤ 100, 0 n ≤ 10^6, 0 primes[i] 1000 。 第 n 個(gè)超級(jí)丑數(shù)確保在 32 位有符整數(shù)范圍內(nèi)。思路這道題看似和動(dòng)態(tài)求極值沒(méi)關(guān)系其實(shí)不然。我們可以預(yù)先生成足夠多的丑數(shù)比如從小到大生成 $N$ 個(gè)然后直接取第 $N$ 個(gè)——但題目數(shù)據(jù)范圍0 n ≤ 10^6預(yù)生成大小為 $10^6$ 的數(shù)組時(shí)間和空間浪費(fèi)都很嚴(yán)重而且如何高效生成也是個(gè)問(wèn)題。通過(guò)丑數(shù)的定義超級(jí)丑數(shù)一定可以寫(xiě)成如下形式if primes [a,b,c,....] then f(ugly) a * x1 * b * x2 * c * x3 ... 其中 x1x2x3 均為正整數(shù)。不妨先將問(wèn)題簡(jiǎn)化考慮題目給的例子[2,7,13,19]可以用四個(gè)指針來(lái)處理直接看代碼public class Solution { public int solve(int n) { int ans[]new int[n5]; ans[0]1; int p10,p20,p30,p40; for(int i1;in;i){ ans[i]Math.min(ans[p1]*2,Math.min(ans[p2]*7,Math.min(ans[p3]*13,ans[p4]*19))); if(ans[i]ans[p1]*2) p1; if(ans[i]ans[p2]*7) p2; if(ans[i]ans[p3]*13) p3; if(ans[i]ans[p3]*19) p4; } return ans[n-1]; } }這個(gè)技巧可以稱之為多路歸并后文「三個(gè)技巧」小節(jié)會(huì)再次用堆來(lái)優(yōu)化它。由于指針是動(dòng)態(tài)的、且指針數(shù)量與primes數(shù)組長(zhǎng)度一致這題也可以看作一個(gè)狀態(tài)機(jī)用記憶化遞歸或動(dòng)態(tài)規(guī)劃解決而這里介紹一種堆的解法相比于動(dòng)態(tài)規(guī)劃個(gè)人認(rèn)為更簡(jiǎn)單、更符合直覺(jué)。實(shí)際上我們可以動(dòng)態(tài)維護(hù)一個(gè)當(dāng)前最小的超級(jí)丑數(shù)找到第一個(gè)將其移除再找下一個(gè)當(dāng)前最小的超級(jí)丑數(shù)也就是全局第二小的超級(jí)丑數(shù)。這樣經(jīng)過(guò) n 輪就得到了第 n 小的超級(jí)丑數(shù)。這種動(dòng)態(tài)維護(hù)極值的場(chǎng)景正是堆的用武之地。以題目給的例子[2,7,13,19]來(lái)說(shuō)將[2,7,13,19]依次入堆出堆一個(gè)數(shù)字也就是 2這時(shí)取到了第一個(gè)超級(jí)丑數(shù)接著將 2 和[2,7,13,19]的乘積也就是[4,14,26,38]依次入堆如此反復(fù)直到取到第 n 個(gè)超級(jí)丑數(shù)。上述正確性是毋庸置疑的每次堆都可以取到最小的每次也會(huì)將最小的從堆中移除因此取 n 次自然就是第 n 小的超級(jí)丑數(shù)。堆的解法唯一需要注意的是去重比如2 * 13 26而13 * 2也是 26不能將 26 入堆兩次。解決方法也很簡(jiǎn)單要么使用哈希表記錄全部已經(jīng)取出的數(shù)對(duì)已經(jīng)取出的數(shù)字不再取另一種方法是記錄上一次取出的數(shù)由于取出的數(shù)字是按照數(shù)字大小不嚴(yán)格遞增的只需要拿上次取出的數(shù)和本次取出的數(shù)比較一下即可。代碼Javaclass Solution { public int nthSuperUglyNumber(int n, int[] primes) { PriorityQueueLong queuenew PriorityQueue(); int count 0; long ans 1; queue.add(ans); while (count n) { ansqueue.poll(); while (!queue.isEmpty() ans queue.peek()) { queue.poll(); } count; for (int i 0; i primes.length ; i) { queue.offer(ans * primes[i]); } } return (int)ans; } }ans初始化為 1 的作用相當(dāng)于虛擬頭僅僅起到了簡(jiǎn)化操作的作用。小結(jié)堆的中心就一個(gè)動(dòng)態(tài)求極值。求極值無(wú)非是最大值或最小值求最大值用大頂堆求最小值用小頂堆。而實(shí)際上如果沒(méi)有「動(dòng)態(tài)」兩個(gè)字很多情況下沒(méi)有必要使用堆——比如可以一次遍歷找出最大值。難點(diǎn)恰恰在于「動(dòng)態(tài)」這個(gè)點(diǎn)不容易看出來(lái)這需要你先對(duì)問(wèn)題進(jìn)行分析分析出這道題其實(shí)就是動(dòng)態(tài)求極值那么使用堆來(lái)優(yōu)化就應(yīng)被想到。類似的例子還有很多后文「三個(gè)技巧」會(huì)做更多講解。倉(cāng)庫(kù)中也有大量同類題解可供對(duì)照練習(xí)例如 295. 數(shù)據(jù)流的中位數(shù)、215. 數(shù)組中的第 K 個(gè)最大元素、378. 有序矩陣中第 K 小的元素。兩種實(shí)現(xiàn)跳表與二叉堆上面簡(jiǎn)單提到了堆的幾種實(shí)現(xiàn)。這里介紹兩種常見(jiàn)的實(shí)現(xiàn)一種是基于鏈表的實(shí)現(xiàn)——跳表另一種是基于數(shù)組的實(shí)現(xiàn)——二叉堆。使用跳表的實(shí)現(xiàn)如果算法沒(méi)有經(jīng)過(guò)精雕細(xì)琢性能會(huì)不太穩(wěn)定且在數(shù)據(jù)量大的情況下內(nèi)存占用會(huì)明顯增加。因此本專題僅詳細(xì)講述二叉堆的實(shí)現(xiàn)對(duì)于跳表實(shí)現(xiàn)僅講述基本原理。跳表以空間換時(shí)間的有序鏈表跳表也是一種數(shù)據(jù)結(jié)構(gòu)在面試中出現(xiàn)的頻率不大但在工業(yè)中經(jīng)常被用到。其設(shè)計(jì)思路值得學(xué)習(xí)比如空間換時(shí)間的思想、效率的取舍問(wèn)題等。前面提到應(yīng)付插隊(duì)問(wèn)題是設(shè)計(jì)堆時(shí)應(yīng)該考慮的首要問(wèn)題。堆的跳表實(shí)現(xiàn)是如何解決的呢我們知道不借助額外空間的情況下在鏈表中查找一個(gè)值需要按順序一個(gè)個(gè)查找時(shí)間復(fù)雜度為 $O(N)$其中 $N$ 為鏈表長(zhǎng)度。當(dāng)鏈表長(zhǎng)度很大時(shí)這種時(shí)間很難接受。一種常見(jiàn)的優(yōu)化方式是建立哈希表將所有節(jié)點(diǎn)都放到哈希表中以空間換時(shí)間將查找復(fù)雜度降到 $O(1)$但空間復(fù)雜度為 $O(N)$。不過(guò)為了防止鏈表出現(xiàn)重復(fù)節(jié)點(diǎn)需要先序列化節(jié)點(diǎn)再建立哈希表空間占用會(huì)更高更重要的是哈希表只能根據(jù) key 獲取內(nèi)容不能解決查找極值的問(wèn)題。為了解決上面的問(wèn)題跳表應(yīng)運(yùn)而生。做法是從鏈表中每?jī)蓚€(gè)元素抽出來(lái)加一級(jí)索引一級(jí)索引指向原始鏈表通過(guò)一級(jí)索引節(jié)點(diǎn)的down指針可以找到原始鏈表的對(duì)應(yīng)節(jié)點(diǎn)。注意這個(gè)算法要求鏈表是有序的。例如查找 10先在一級(jí)跳表中搜索到 7發(fā)現(xiàn)下一個(gè) 18 大于 10即要找的 10 在兩者之間然后通過(guò)down指針回到原始鏈表通過(guò)原始鏈表的next指針找到 10。這個(gè)例子看不出性能提升但如果元素繼續(xù)增多、繼續(xù)增加索引層數(shù)二級(jí)、三級(jí)……索引使鏈表能夠?qū)崿F(xiàn)二分查找就能獲得更好的效率當(dāng)然也需付出額外空間的代價(jià)?？梢园烟硇蜗蟮叵胂鬄橥嬗螒虻拇鏅n一個(gè)游戲有 10 關(guān)想玩第 5 關(guān)的某個(gè)地方可以直接從第 5 關(guān)開(kāi)始甚至可以設(shè)置很多存檔直接選擇離目標(biāo)更近的存檔——這就相當(dāng)于跳表的二級(jí)索引。跳表的時(shí)間復(fù)雜度和空間復(fù)雜度由于時(shí)間復(fù)雜度 索引的高度 × 平均每層索引遍歷元素的個(gè)數(shù)高度大概為 $\log n$且每層遍歷的元素是常數(shù)因此時(shí)間復(fù)雜度為 $O(\log n)$?？臻g復(fù)雜度等同于索引節(jié)點(diǎn)的個(gè)數(shù)以每?jī)蓚€(gè)節(jié)點(diǎn)建立一個(gè)索引為例大約是 $n/2 n/4 n/8 … 8 4 2$因此空間復(fù)雜度是 $O(n)$當(dāng)然每三個(gè)節(jié)點(diǎn)建立一個(gè)索引會(huì)更省空間但復(fù)雜度不變。理解了上面的內(nèi)容使用跳表實(shí)現(xiàn)堆就不難了入堆根據(jù)索引插到鏈表中并更新索引可選出堆刪除頭部或尾部并更新索引可選。如果想檢測(cè)自己的跳表實(shí)現(xiàn)是否有問(wèn)題可以去 LeetCode 的 1206. 設(shè)計(jì)跳表 檢測(cè)。二叉堆一顆特殊的完全二叉樹(shù)二叉堆的實(shí)現(xiàn)本專題僅講解最核心的兩個(gè)操作heappop出堆和heappush入堆。實(shí)現(xiàn)之后的使用效果大概是這樣h min_heap() h.build_heap([5, 6, 2, 3]) h.heappush(1) h.heappop() # 1 h.heappop() # 2 h.heappush(1) h.heappop() # 1 h.heappop() # 3基本原理本質(zhì)上來(lái)說(shuō)二叉堆就是一顆特殊的完全二叉樹(shù)它的特殊性只體現(xiàn)在一點(diǎn)父節(jié)點(diǎn)的權(quán)值不大于兒子的權(quán)值小頂堆。這一點(diǎn)需要牢記一切的一切都源于這句話。由于父節(jié)點(diǎn)的權(quán)值不大于兒子的權(quán)值很自然能推導(dǎo)出樹(shù)的根節(jié)點(diǎn)就是最小值這就起到了堆「取極值」的作用。那么「動(dòng)態(tài)性」呢二叉堆是怎么做到的出堆下沉如果將樹(shù)的根節(jié)點(diǎn)出堆根節(jié)點(diǎn)就空缺了應(yīng)該讓第二小的頂替上去。如果僅僅是刪除一個(gè)堆就會(huì)變成兩個(gè)堆問(wèn)題變復(fù)雜了。一個(gè)常見(jiàn)的操作是把根結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)交換。但新的根結(jié)點(diǎn)可能不滿足堆性質(zhì)父節(jié)點(diǎn)的權(quán)值不大于兒子的權(quán)值此時(shí)只需要將新的根節(jié)點(diǎn)下沉到正確位置即可。這里的「正確位置」指的依然是那句堆性質(zhì)如果不滿足就繼續(xù)下沉直到滿足。需要注意的是根節(jié)點(diǎn)往下下沉?xí)r有兩個(gè)方向可供選擇下沉到左子節(jié)點(diǎn)還是右子節(jié)點(diǎn)以小頂堆來(lái)說(shuō)答案應(yīng)該是下沉到較小的子節(jié)點(diǎn)處否則會(huì)錯(cuò)失正確答案。以下面的堆為例如果下沉到右子節(jié)點(diǎn) 4就無(wú)法得到正確的堆頂 3因此需要下沉到左子節(jié)點(diǎn)。有的同學(xué)可能有疑問(wèn)彈出根節(jié)點(diǎn)前堆滿足性質(zhì)彈出之后經(jīng)過(guò)下沉操作一定還滿足嗎答案是肯定的。由于最后的葉子節(jié)點(diǎn)被提到了根節(jié)點(diǎn)它最終在哪是不確定的但經(jīng)過(guò)上面的操作可以看出其下沉路徑上的節(jié)點(diǎn)一定都滿足堆的性質(zhì)不在下沉路徑上的節(jié)點(diǎn)都保持了堆之前的相對(duì)關(guān)系因此也滿足堆的性質(zhì)。因此彈出根節(jié)點(diǎn)后經(jīng)過(guò)下沉操作一定仍然滿足堆的性質(zhì)。時(shí)間復(fù)雜度方面可以證明下沉和樹(shù)的高度成正相關(guān)因此時(shí)間復(fù)雜度為 $O(h)$其中 $h$ 為樹(shù)高而由于二叉堆是完全二叉樹(shù)樹(shù)高大約是 $\log N$其中 $N$ 為樹(shù)中的節(jié)點(diǎn)個(gè)數(shù)。入堆上浮入堆和出堆類似可以直接往樹(shù)的最后插入一個(gè)節(jié)點(diǎn)。之所以這么做其中一個(gè)原因是時(shí)間復(fù)雜度更低——我們是用數(shù)組進(jìn)行模擬的而在數(shù)組尾部添加元素的時(shí)間復(fù)雜度為 $O(1)$。但同樣的這樣的操作可能破壞堆的性質(zhì)。這次不滿足堆的節(jié)點(diǎn)是剛插入的尾部節(jié)點(diǎn)因此不能進(jìn)行下沉操作了需要執(zhí)行上浮操作葉子節(jié)點(diǎn)只能上浮根節(jié)點(diǎn)只能下沉其他節(jié)點(diǎn)既可以下沉又可以上浮。和上面基本類似如果不滿足堆的性質(zhì)將其和父節(jié)點(diǎn)交換上浮繼續(xù)這個(gè)過(guò)程直到滿足。經(jīng)過(guò)這樣的操作其仍是一個(gè)滿足堆性質(zhì)的堆證明過(guò)程與下沉類似不再贅述。需要注意的是由于上浮只需要拿當(dāng)前節(jié)點(diǎn)和父節(jié)點(diǎn)進(jìn)行比對(duì)省去了判斷左右子節(jié)點(diǎn)哪個(gè)更小的過(guò)程因此更加簡(jiǎn)單。數(shù)組表示與核心代碼對(duì)于完全二叉樹(shù)來(lái)說(shuō)使用數(shù)組實(shí)現(xiàn)非常方便因?yàn)榇嬖谌缦伦鴺?biāo)關(guān)系要求數(shù)組從 1 開(kāi)始存儲(chǔ)數(shù)據(jù)這是一種業(yè)界習(xí)慣如果節(jié)點(diǎn)在數(shù)組中的下標(biāo)為i那么其左子節(jié)點(diǎn)下標(biāo)為 $2 \times i$右子節(jié)點(diǎn)為 $2 \times i 1$如果節(jié)點(diǎn)在數(shù)組中的下標(biāo)為i那么父節(jié)點(diǎn)下標(biāo)為i // 2地板除。從 1 開(kāi)始存儲(chǔ)的另外一個(gè)好處是可以將索引 0 的位置空出來(lái)存儲(chǔ)諸如堆大小的信息這是一些大學(xué)教材里的做法。有了上浮/下沉過(guò)程再配合父子節(jié)點(diǎn)坐標(biāo)關(guān)系代碼就呼之欲出了。先看核心的上浮與下沉偽代碼// x 是要上浮的元素從樹(shù)的底部開(kāi)始上浮 private void shift_up(int x) { while (x 1 h[x] h[x / 2]) { // swap 就是交換數(shù)組兩個(gè)位置的值 swap(h[x], h[x / 2]); x / 2; } } // x 是要下沉的元素從樹(shù)的頂部開(kāi)始下沉 private void shift_down(int x) { while (x * 2 n) { // minChild 是獲取更小的子節(jié)點(diǎn)的索引并返回 mc minChild(x); if (h[mc] h[x]) break; swap(h[x], h[mc]); x mc; } }以 Java 為例的完整實(shí)現(xiàn)數(shù)組下標(biāo)從 1 開(kāi)始import java.util.Arrays; import java.util.Comparator; /** * 用完全二叉樹(shù)來(lái)構(gòu)建 堆 * 前置條件 起點(diǎn)為 1 * 那么 子節(jié)點(diǎn)為 i 1 和 i1 1 * 核心方法為 * shiftdown 交換下沉 * shiftup 交換上浮 * build 構(gòu)建堆 */ public class Heap { int size 0; int queue[]; public Heap(int initialCapacity) { if (initialCapacity 1) throw new IllegalArgumentException(); this.queue new int[initialCapacity]; } public Heap(int[] arr) { size arr.length; queue new int[arr.length 1]; int i 1; for (int val : arr) { queue[i] val; } } public void shiftDown(int i) { int temp queue[i]; while ((i 1) size) { int child i 1; // child!size 判斷當(dāng)前元素是否包含右節(jié)點(diǎn) if (child ! size queue[child 1] queue[child]) { child; } if (temp queue[child]) { queue[i] queue[child]; i child; } else { break; } } queue[i] temp; } public void shiftUp(int i) { int temp queue[i]; while ((i 1) 0) { if (temp queue[i 1]) { queue[i] queue[i 1]; i 1; } else { break; } } queue[i] temp; } public int peek() { int res queue[1]; return res; } public int pop() { int res queue[1]; queue[1] queue[size--]; shiftDown(1); return res; } public void push(int val) { if (size queue.length - 1) { queue Arrays.copyOf(queue, size 11); } queue[size] val; shiftUp(size); } public void buildHeap() { for (int i size 1; i 0; i--) { shiftDown(i); } } public static void main(String[] args) { int arr[] new int[]{2,7,4,1,8,1}; Heap heap new Heap(arr); heap.buildHeap(); System.out.println(heap.peek()); heap.push(5); while (heap.size 0) { int num heap.pop(); System.out.printf(num ); } } }小結(jié)堆的實(shí)現(xiàn)有很多基于鏈表的跳表、基于數(shù)組的二叉堆、基于紅黑樹(shù)的實(shí)現(xiàn)等。本專題詳細(xì)講述了二叉堆的實(shí)現(xiàn)不僅因?yàn)樗鼘?shí)現(xiàn)簡(jiǎn)單而且它在很多情況下表現(xiàn)都不錯(cuò)推薦重點(diǎn)掌握二叉堆實(shí)現(xiàn)。對(duì)于二叉堆的實(shí)現(xiàn)核心點(diǎn)就一點(diǎn)始終維護(hù)堆的性質(zhì)不變即「父節(jié)點(diǎn)的權(quán)值不大于兒子的權(quán)值小頂堆」。為了達(dá)到這個(gè)目的需要在入堆和出堆時(shí)使用上浮和下沉操作并恰當(dāng)?shù)赝瓿稍亟粨Q——具體來(lái)說(shuō)上浮過(guò)程與比它大的父節(jié)點(diǎn)進(jìn)行交換下沉過(guò)程與兩個(gè)子節(jié)點(diǎn)中較小的進(jìn)行交換前提是它有子節(jié)點(diǎn)且子節(jié)點(diǎn)比它小。關(guān)于堆化buildHeap這里沒(méi)有做詳細(xì)分析但理解了入堆操作后這其實(shí)很容易——堆化本身就是一個(gè)不斷入堆的過(guò)程只不過(guò)將時(shí)間上離散的操作變成了一次性操作而已。三個(gè)技巧與四大應(yīng)用進(jìn)階解題套路本專題分為兩個(gè)部分第一部分即本文主體講清了「一個(gè)中心」與「兩種實(shí)現(xiàn)」第二部分對(duì)應(yīng) thinkings/heap-2.en.md專門講三個(gè)技巧與四大應(yīng)用這是專門教你怎么解題的掌握了它們力扣中大多數(shù)堆的題目都不在話下。三個(gè)技巧多路歸并上面講超級(jí)丑數(shù)時(shí)其實(shí)已經(jīng)提到了只是沒(méi)有給它命名。多路體現(xiàn)在有多個(gè)候選路代碼中用多個(gè)指針表示歸并體現(xiàn)在結(jié)果可能是多條候選路中的最長(zhǎng)、最短或第 k 個(gè)等需要比較多條路的結(jié)果并根據(jù)題意取舍。倉(cāng)庫(kù)中的 23. 合并 K 個(gè)排序鏈表 正是這一技巧的經(jīng)典載體把 k 個(gè)有序鏈表的頭結(jié)點(diǎn)放入小頂堆每次彈出最小節(jié)點(diǎn)并推入其后繼即可在 $O(N\log k)$ 時(shí)間內(nèi)完成合并。固定堆把堆的大小固定為 k 不變代碼上通過(guò)「推入一個(gè)的同時(shí)彈出一個(gè)」來(lái)實(shí)現(xiàn)初始時(shí)逐個(gè)推入使堆大小達(dá)到 k嚴(yán)格來(lái)說(shuō)是維護(hù)堆的大小不大于 k。固定大小為 k 的大頂堆可以快速求第 k 小的數(shù)堆內(nèi)維護(hù)的是全局最小的 k 個(gè)數(shù)堆頂是其中最大的即第 k 小反之固定大小為 k 的小頂堆可以快速求第 k 大的數(shù)。經(jīng)典應(yīng)用如 295. 數(shù)據(jù)流的中位數(shù)維護(hù)兩個(gè)固定堆——大頂堆放較小的 $(n1)/2$ 個(gè)數(shù)、小頂堆放較大的 $n - (n1)/2$ 個(gè)數(shù)兩堆堆頂即為中位數(shù)addNum與findMedian均可在 $O(\log n)$ / $O(1)$ 內(nèi)完成。倉(cāng)庫(kù)題解 295.find-median-from-data-stream.md 對(duì)該題有完整的雙堆推導(dǎo)與代碼。事后小諸葛指先按某種順序處理數(shù)據(jù)、事后再用堆做修正的技巧具體內(nèi)容詳見(jiàn)續(xù)篇 thinkings/heap-2.en.md。四大應(yīng)用topK求第 k 大/第 k 小、最小的 k 個(gè)數(shù)等是固定堆技巧的直接應(yīng)用倉(cāng)庫(kù)中的 215. 數(shù)組中的第 K 個(gè)最大元素 與 378. 有序矩陣中第 K 小的元素 都是典型例題。帶權(quán)最短距離即 dijkstra 算法用優(yōu)先隊(duì)列做 BFS 處理帶權(quán)圖最短路徑這正是前面「隊(duì)列 VS 優(yōu)先隊(duì)列」一節(jié)強(qiáng)調(diào)過(guò)的場(chǎng)景。因子分解如超級(jí)丑數(shù)、丑數(shù)相關(guān)題解 等通過(guò)堆動(dòng)態(tài)維護(hù)最小因子組合生成序列。堆排序建堆后不斷pop堆頂即可得到有序序列——上文的Heap.main演示的正是這個(gè)過(guò)程輸出1 2 4 5 7 8。倉(cāng)庫(kù)配套資源導(dǎo)航本專題在倉(cāng)庫(kù)中有完整的中英文文檔與配套題解可按需深入閱讀專題第一講thinkings/heap.en.md英文版與 thinkings/heap.md中文版覆蓋「一個(gè)中心、兩種實(shí)現(xiàn)」即本文內(nèi)容專題第二講thinkings/heap-2.en.md 與 thinkings/heap-2.md覆蓋「三個(gè)技巧、四大應(yīng)用」的詳細(xì)題解如 295、857、1439 等 hard 題目倉(cāng)庫(kù)配套題解295.find-median-from-data-stream.md雙堆求中位數(shù)、23.merge-k-sorted-lists.md多路歸并合并 K 個(gè)鏈表、215.kth-largest-element-in-an-array.md 與 378.kth-smallest-element-in-a-sorted-matrix.mdtopK 類、513.find-bottom-left-tree-value.md優(yōu)先隊(duì)列實(shí)現(xiàn) BFS 的演示相關(guān)思維導(dǎo)圖與圖示可參考 assets/thinkings/min-heap.png小頂堆結(jié)構(gòu)示意圖、assets/thinkings/max-heap.svg大頂堆結(jié)構(gòu)示意圖?？偨Y(jié)堆專題看似難困難題占比近半但解題核心其實(shí)高度收斂識(shí)別場(chǎng)景凡是「數(shù)據(jù)在動(dòng)態(tài)變化、需要反復(fù)取極值」的問(wèn)題優(yōu)先想到堆理解本質(zhì)堆是一顆特殊的完全二叉樹(shù)父節(jié)點(diǎn)權(quán)值不大于子節(jié)點(diǎn)根節(jié)點(diǎn)即極值入堆/出堆通過(guò)上浮/下沉維持堆性質(zhì)復(fù)雜度均為 $O(\log N)$套用套路多路歸并、固定堆、事后小諸葛三個(gè)技巧覆蓋 topK、帶權(quán)最短距離、因子分解、堆排序四大應(yīng)用幾乎可以解決力扣上絕大多數(shù)與堆相關(guān)的題目。把「一個(gè)中心、兩種實(shí)現(xiàn)、三個(gè)技巧、四大應(yīng)用」這條主線吃透再配合倉(cāng)庫(kù)中的中英文專題文檔與逐題題解反復(fù)演練堆就不再是攔路虎。【免費(fèi)下載鏈接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode題解記錄自己的leetcode解題之路。)項(xiàng)目地址: https://gitcode.com/gh_mirrors/le/leetcode創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考