看到“堆”這個詞很多程序員都會愣一下因?yàn)樗诓煌瑘鼍袄锎淼臇|西完全不一樣。做數(shù)據(jù)結(jié)構(gòu)的課程作業(yè)時老師讓你手寫堆排序深夜排查服務(wù)內(nèi)存暴漲時你用jmap看的是Java堆寫C語言時malloc分配在堆上刷面試題又會看到堆外內(nèi)存、DirectBuffer、編譯器堆空間不足這些詞。更別提面試時主考官輕描淡寫地來一句“用堆實(shí)現(xiàn)一個TopK”而你腦中還在糾結(jié)到底該用大頂堆還是小頂堆。這篇文章準(zhǔn)備把這些概念一次性拆開講清楚數(shù)據(jù)結(jié)構(gòu)里的堆、進(jìn)程內(nèi)存里的堆、語言運(yùn)行時里的堆外內(nèi)存以及圍繞堆的基礎(chǔ)操作和實(shí)戰(zhàn)方法全部帶過一遍。適合正在學(xué)數(shù)據(jù)結(jié)構(gòu)的在校生、準(zhǔn)備算法面試的開發(fā)者以及被內(nèi)存問題折騰過、想徹底搞懂“堆和棧”到底差在哪的工程師。內(nèi)容不追求講得特別深但會盡量把“為什么這樣設(shè)計(jì)”“為什么用這個堆”這類底層邏輯講明白幫你以后再看到帶“堆”字的概念都能立刻對號入座。1. 堆的兩副面孔數(shù)據(jù)結(jié)構(gòu)和內(nèi)存區(qū)域的區(qū)別1.1 同一個詞兩種完全不同的體系先說一個不少人踩過的坑數(shù)據(jù)結(jié)構(gòu)里的“堆”和操作系統(tǒng)里的“堆區(qū)”其實(shí)只是恰好叫同一個名字在英文里也是不同的詞源。數(shù)據(jù)結(jié)構(gòu)里的堆叫Heap最初來源于“堆在一起的東西”指的是一種按特定順序組織的樹形結(jié)構(gòu)內(nèi)存管理里的堆區(qū)也叫Heap指的是動態(tài)內(nèi)存分配所在的區(qū)域概念來源是“一堆空閑內(nèi)存塊”這個印象。但為什么偏偏都叫Heap有一個流傳很廣的說法是早期的內(nèi)存分配器把空閑內(nèi)存塊像“堆疊”起來管理所以就叫heap。再加上數(shù)據(jù)結(jié)構(gòu)里二叉堆通常用數(shù)組存放數(shù)據(jù)也是“堆疊”在數(shù)組里的名字就這么混著叫開了。這個巧合在面試中經(jīng)常把人繞暈面試官先問“堆排序的原理”接著又問“進(jìn)程的內(nèi)存布局里堆和棧有什么區(qū)別”看起來是一個知識點(diǎn)實(shí)際上需要你用兩套知識體系去回答。把這兩套體系分開記是學(xué)習(xí)的第一步。數(shù)據(jù)結(jié)構(gòu)中的堆解決的是“如何高效取最大/最小元素”的問題對應(yīng)的操作有插入、刪除、建堆內(nèi)存管理中的堆解決的是“程序運(yùn)行時如何動態(tài)申請和釋放內(nèi)存”的問題對應(yīng)的概念有malloc、垃圾回收、內(nèi)存泄漏、堆外內(nèi)存。兩者之間沒有公式上的直接聯(lián)系但徹底理解之后你會發(fā)現(xiàn)它們的核心思想都是“對一塊區(qū)域做高效管理”。1.2 為什么堆這么好用卻總讓人犯迷糊如果要我總結(jié)大概有三個原因。概念多而近。大頂堆、小頂堆、優(yōu)先隊(duì)列、堆排序、堆外內(nèi)存、編譯器的堆空間不足……這些詞放在一起既像父子又像兄弟沒有一條主線確實(shí)容易暈。建議初學(xué)者先抓一類優(yōu)先掌握數(shù)據(jù)結(jié)構(gòu)堆因?yàn)樗撬惴}里最常出現(xiàn)的考點(diǎn)等有了手感再學(xué)內(nèi)存堆。維度跨度大。從數(shù)據(jù)結(jié)構(gòu)跳到操作系統(tǒng)再從理論分析跳到實(shí)際排障每一步都要求讀者換一種視角。我之前帶過幾個實(shí)習(xí)生在紙上寫堆排序手到擒來但一看到“Error: java.lang.OutOfMemoryError: Java heap space”就以為是自己寫的堆出了問題實(shí)際上兩者八竿子打不著。資料里默認(rèn)你什么都會。很多文章上來就講數(shù)組下標(biāo)i的左孩子是2i1卻沒說清楚下標(biāo)從0開始還是從1開始講優(yōu)先隊(duì)列時默認(rèn)你已經(jīng)知道為什么Python的heapq是小頂堆而C的priority_queue卻是大頂堆。這篇文章會把容易默認(rèn)跳過的細(xì)節(jié)補(bǔ)上讓你以后看任何資料都能秒懂對方在說什么。2. 算法世界的堆類別、存儲方式和經(jīng)典應(yīng)用2.1 大頂堆和小頂堆不僅僅是“根最大和根最小”數(shù)據(jù)結(jié)構(gòu)里的堆最常見的是二叉堆。二叉堆必須滿足兩個條件第一它是一棵完全二叉樹也就是除了最后一層其它層必須填滿且最后一層的節(jié)點(diǎn)都靠左排列第二節(jié)點(diǎn)和子節(jié)點(diǎn)之間滿足堆序性通常分為大頂堆和小頂堆。大頂堆要求每個父節(jié)點(diǎn)的值都大于等于它的子節(jié)點(diǎn)因此堆頂一定是整個堆的最大值小頂堆則相反堆頂是最小值。這里容易產(chǎn)生一個誤區(qū)有人會把堆和二叉搜索樹混在一起以為左子樹一定比右子樹小。實(shí)際上堆的兄弟節(jié)點(diǎn)之間沒有大小約束只有父子之間滿足堆序性。你可以把大頂堆理解成一個“家長永遠(yuǎn)比孩子拿得多”的組織但同一層之間誰拿得多誰拿得少完全隨意。堆的平衡性來自完全二叉樹。因?yàn)闃涞母叨仁冀K維持在log2(n)級別所以插入、刪除堆頂元素都只需要O(log n)的時間。這個復(fù)雜度優(yōu)勢是堆在算法問題中廣泛使用的根基。你可以對比一下普通數(shù)組找最大值要O(n)插入要移動大量元素用二叉堆則能在動態(tài)數(shù)據(jù)流中始終以很小的成本維護(hù)“當(dāng)前最大/最小”的信息。2.2 數(shù)組存儲堆三個必須牢記的下標(biāo)公式二叉堆一般不用鏈表節(jié)點(diǎn)表示而是用數(shù)組原因就在于完全二叉樹的結(jié)構(gòu)天然適合連續(xù)存儲。如果你用節(jié)點(diǎn)指針反而會浪費(fèi)大量空間還要維護(hù)額外的節(jié)點(diǎn)對象所以堆的實(shí)現(xiàn)幾乎都會基于數(shù)組。假設(shè)根節(jié)點(diǎn)存放在數(shù)組下標(biāo)0的位置那么對于下標(biāo)i的節(jié)點(diǎn)父節(jié)點(diǎn)下標(biāo)parent(i) (i - 1) / 2左孩子下標(biāo)left(i) 2 * i 1右孩子下標(biāo)right(i) 2 * i 2如果根節(jié)點(diǎn)從1開始存放公式會變成父節(jié)點(diǎn)下標(biāo)parent(i) i / 2左孩子下標(biāo)left(i) 2 * i右孩子下標(biāo)right(i) 2 * i 1很多人面試手寫堆時容易在這里翻車。寫代碼之前先明確數(shù)組的0號位置是否參與堆的存儲。如果從0開始那么左孩子是2i1不是2i如果從1開始則0號位置要么空著要么只作為占位符存在。兩套公式一旦混用插入刪除時會出現(xiàn)大量越界和找不到父節(jié)點(diǎn)的問題。我自己更推薦在實(shí)際刷題時統(tǒng)一用“0號位參與存儲”的習(xí)慣因?yàn)镻ython的heapq內(nèi)部就是這樣的邏輯C的priority_queue底層容器vector默認(rèn)也是從0開始。如果你默認(rèn)Java、C常用寫法沒問題切到Python時也順理成章。2.3 插入和刪除上浮與下沉堆操作的核心靈魂堆的插入操作并不復(fù)雜把新元素追加到數(shù)組尾部然后“上浮”。上浮的意思是不斷拿當(dāng)前節(jié)點(diǎn)和父節(jié)點(diǎn)比較如果違反了堆序性就交換位置直到到達(dá)堆頂或者滿足堆序。這個過程很像在一個已經(jīng)排好隊(duì)的隊(duì)伍里插入一個新成員如果新成員比前面的領(lǐng)導(dǎo)級別還高就一路往前換。刪除堆頂元素則是另一個思路先把堆頂元素和數(shù)組最后一個元素交換然后讓這個臨時堆頂“下沉”。下沉?xí)r每次和左右孩子中較大/較小的那個比較一旦不滿足堆序就交換持續(xù)走到葉子節(jié)點(diǎn)。之所以選數(shù)組最后一個元素來頂替堆頂是因?yàn)槎岩笸耆鏄浣Y(jié)構(gòu)只有最后一個元素被拿走后剩余節(jié)點(diǎn)仍然能保持完全二叉樹的樣子。上浮和下沉這兩個動作是所有堆操作的發(fā)動機(jī)。無論是最小堆、最大堆還是后面會說的優(yōu)先隊(duì)列、堆排序本質(zhì)上都是在圍繞這兩個動作做文章。2.4 堆排序復(fù)雜度低但實(shí)際排序?yàn)槭裁床怀Ｓ盟雅判蚴且粋€基于大頂堆的排序方法先把數(shù)組構(gòu)建成一個大頂堆然后把堆頂元素和末尾元素交換再把剩下的n-1個元素重新調(diào)整成大頂堆。重復(fù)這個過程數(shù)組末尾就會逐步累積有序序列。堆排序的時間復(fù)雜度穩(wěn)定在O(n log n)空間復(fù)雜度是O(1)看上去很美。但實(shí)際開發(fā)中主流語言內(nèi)置的排序函數(shù)幾乎都不會直接使用堆排序而是選快速排序的改進(jìn)版比如C的introsort先快排遞歸過深再轉(zhuǎn)堆排序。原因有兩個第一堆排序是不穩(wěn)定排序。因?yàn)槎雅判驎诮粨Q過程中把相同元素的相對順序打亂而很多業(yè)務(wù)場景需要保持穩(wěn)定性排序。第二堆排序的緩存局部性很差。它訪問數(shù)組下標(biāo)時是“跳躍式”的比如訪問下標(biāo)2、4、8……而快速排序是順序分區(qū)掃描CPU緩存命中率更高。實(shí)際跑起來快排往往比堆排序快。所以堆排序的重點(diǎn)不在“自己寫一個排序”而在于理解“怎么原地建堆”“怎么反復(fù)取最大元素”的思想。后續(xù)的優(yōu)先隊(duì)列、定時器、Dijkstra算法加速都依賴這套取堆頂?shù)哪芰Α?.5 視野打開不只是二叉堆二叉堆是最常見的堆但不是唯一的堆。比如“D叉堆”讓每個節(jié)點(diǎn)有多個孩子降低樹高但增大了每個節(jié)點(diǎn)找最值孩子時的比較次數(shù)又比如“配對堆”在并查集和圖算法中能支持更高效地合并兩個堆“斐波那契堆”則把某些操作的均攤復(fù)雜度降到了O(1)。新手不用急著把非二叉堆都學(xué)會但可以知道一個事實(shí)面試和工作中用到最多的還是二叉堆因?yàn)樗唵?、可靠、?nèi)存占用低。像多路歸并排序里用到的k路歸并堆本質(zhì)上就是一個小頂堆幫你從k個有序鏈表中每次取最小的頭節(jié)點(diǎn)。這些應(yīng)用只要能把二叉堆吃透后面都很順。3. 運(yùn)行時內(nèi)存的堆棧和堆的博弈3.1 棧負(fù)責(zé)執(zhí)行堆負(fù)責(zé)生存算法題講完了再說說程序真正運(yùn)行時的內(nèi)存布局?，F(xiàn)代操作系統(tǒng)加載一個進(jìn)程后會為它分配一塊虛擬地址空間從低地址到高地址大致包含代碼段、數(shù)據(jù)段、堆區(qū)、內(nèi)存映射區(qū)、棧區(qū)。這里的堆區(qū)就是malloc、new或JVM堆對象分配內(nèi)存的地方。棧Stack和堆Heap最大的區(qū)別在于管理方式。棧由編譯器自動管理每次函數(shù)調(diào)用會創(chuàng)建棧幀局部變量、函數(shù)參數(shù)、返回地址都放在棧幀里函數(shù)返回時棧幀自動銷毀。堆則沒有這種“自動按作用域銷毀”的機(jī)制在C/C里需要手動free/delete不及時釋放就會內(nèi)存泄漏在Java、Go這類帶GC的語言里雖然由垃圾收集器回收但回收時機(jī)并不完全可控。打個比方棧很像廚房的操作臺你從一個菜做到下一個菜上一個菜用完的盤子會自動被收走速度快、空間相對固定堆則像一個大型倉庫你可以隨手去倉庫里領(lǐng)一塊區(qū)域存放需要長期保留的東西但必須定期自己清理或者依賴專業(yè)的倉庫管理員GC來幫你清理。?？臻g在大多數(shù)系統(tǒng)中只有幾MB到十幾MB而堆空間卻可以設(shè)置到幾個GB甚至更多。3.2 動手看地址棧在高處堆在低處光背概念很難有直觀感受我建議你在自己的Linux環(huán)境跑下面這段C代碼#include stdio.h #include stdlib.h int main() { int stack_var 42; int *heap_var (int *)malloc(sizeof(int)); *heap_var 42; printf(stack addr: %p\n, (void *)stack_var); printf(heap addr: %p\n, (void *)heap_var); free(heap_var); return 0; }我在一臺常見的x86-64 Linux機(jī)器上得到的輸出大致是stack addr: 0x7ffc9d3d4a2c heap addr: 0x55b03b8652a0可以看到棧變量地址明顯比堆變量地址高很多。原因是進(jìn)程的棧區(qū)位于虛擬地址空間的高地址區(qū)域并且棧是向下增長的堆區(qū)則在相對低的位置向高地址方向增長。棧和堆看上去是“面對面生長”這也是“棧溢出會把?？臻g耗盡”這類問題出現(xiàn)的原因。很多做Java開發(fā)的朋友可能沒寫過C語言沒關(guān)系你也可以用JVM參數(shù)打印進(jìn)程地址效果類似。理解這塊還方便你想通另一個問題為什么棧分配快、堆分配慢因?yàn)闂７峙渲恍枰苿訔Ｖ羔樢粭l指令就完成了而堆分配需要分配器去尋找合適的空閑內(nèi)存塊還要處理并發(fā)加鎖自然慢很多。3.3 堆外內(nèi)存被繞開的“堆”Java程序員一定見過堆外內(nèi)存這個詞尤其在Netty、Kafka這類高性能框架的相關(guān)文章里。它指的是JVM堆之外的內(nèi)存最典型的是java.nio.DirectByteBuffer分配的“直接內(nèi)存”。JVM在向操作系統(tǒng)發(fā)起讀寫操作時底層會調(diào)用native的IO函數(shù)。如果數(shù)據(jù)放在Java堆內(nèi)那么native IO往往不能直接訪問Java堆內(nèi)存的地址需要把數(shù)據(jù)先拷貝到一塊操作系統(tǒng)能直接操作的內(nèi)存中而如果你用的是堆外的DirectByteBuffer數(shù)據(jù)本身就在堆外IO可以直接拿這塊地址讀寫少了一次內(nèi)存拷貝。于是就有了一個面試高頻題為什么Netty要使用堆外內(nèi)存答案就是減少拷貝提高IO性能。堆外內(nèi)存不受JVM的-Xmx限制但受本機(jī)物理內(nèi)存以及參數(shù)-XX:MaxDirectMemorySize限制在未顯式設(shè)置時MaxDirectMemorySize默認(rèn)與-Xmx一樣大。管理不當(dāng)就會出現(xiàn)“Direct buffer memory”的OutOfMemoryError而且這種OOM還不一定被GC日志里的堆信息體現(xiàn)出來排查起來比較迷。我見過不少線上事故都是因?yàn)橹恢腊?Xmx調(diào)大卻忘記了Netty直接內(nèi)存的用量暴漲。定位時可以通過jcmd pid VM.native_memory summary來查看內(nèi)存分布也可以在JVM參數(shù)里加-XX:MaxDirectMemorySize給一個明確上限。堆外內(nèi)存的性能優(yōu)勢讓它不可不用但它絕不意味著“可以無限申請”手動釋放和池化如Netty的PooledByteBufAllocator是一定要做好的。3.4 堆空間不足是不是只能加內(nèi)存不管是C的malloc失敗、Python的MemoryError還是Java的java.lang.OutOfMemoryError遇到堆空間不足大多數(shù)人的第一反應(yīng)是加內(nèi)存條或調(diào)大堆上限。這個方向不能說全錯但很多時候并不會真正解決問題。遇到堆空間不足先分清兩種情況一種是程序當(dāng)前真的需要很大的內(nèi)存而且業(yè)務(wù)是有意義的比如加載大模型、處理超大圖片這時擴(kuò)容是合理的另一種是程序存在內(nèi)存泄漏或者對象被無意識持有了比如把每次請求的臨時數(shù)據(jù)都塞進(jìn)了一個靜態(tài)List導(dǎo)致堆被慢慢填滿這時盲目擴(kuò)容只是推遲崩潰時間甚至?xí)宖ull GC更加頻繁。排查Java堆問題的常規(guī)路徑是先看GC日志確認(rèn)OOM前是不是頻繁Full GC、堆內(nèi)存是否一直無法回收再用jmap -dump:formatb,fileheap.bin pid導(dǎo)一份堆快照用MAT等分析工具看Dominator Tree找出哪些對象占據(jù)了最多內(nèi)存再順著引用鏈找到誰在持有這些對象。排查Python內(nèi)存問題也可以用tracemallocimport tracemalloc tracemalloc.start() # 這里運(yùn)行你想要監(jiān)控的業(yè)務(wù)代碼 snapshot tracemalloc.take_snapshot() top_stats snapshot.statistics(lineno) for stat in top_stats[:10]: print(stat)它會告訴你每一行代碼累計(jì)分配了多少內(nèi)存。通過對比幾次快照就能看出內(nèi)存是在哪個模塊里持續(xù)增長的。4. 實(shí)戰(zhàn)拆解用Python實(shí)現(xiàn)堆和TopK4.1 語言自帶的堆Python heapq的正確打開方式Python把二叉堆放在heapq模塊中默認(rèn)是小頂堆。這意味著堆頂元素永遠(yuǎn)是序列里最小的元素。常用的API如下import heapq nums [3, 1, 4, 1, 5, 9, 2, 6] # 原地建堆O(n) heapq.heapify(nums) # 入堆 heapq.heappush(nums, 0) # 出堆每次彈出當(dāng)前最小值 min_val heapq.heappop(nums) # 先替換堆頂再入堆相當(dāng)于一步完成poppush常用于TopK heapq.heapreplace(nums, 10) # 一行拿到最大的3個數(shù) print(heapq.nlargest(3, nums)) # 一行拿到最小的3個數(shù) print(heapq.nsmallest(3, nums))如果要用大頂堆Python沒有直接內(nèi)置最常用的技巧是存相反數(shù)入堆時存-x出堆時取-x。由此得到的就是原本意義上的最大值。例如heap [] for x in [3, 1, 4, 1, 5, 9]: heapq.heappush(heap, -x) max_val -heapq.heappop(heap) print(max_val) # 9這里容易出錯的地方是出堆之后別忘了做一次符號翻轉(zhuǎn)。我看到很多初學(xué)者寫了半天最后打印的是負(fù)數(shù)然后滿臉疑惑地來問“為什么我的最大值是-9”。4.2 手寫一個最小堆面試不再心虛雖然實(shí)際開發(fā)中直接調(diào)heapq就行但面試手寫堆的題目仍然常見特別是考察插入、刪除和建堆。寫一個簡單的最小堆類會讓你對堆的理解上一個臺階。class MinHeap: def __init__(self): self.heap [] def push(self, val): self.heap.append(val) self._sift_up(len(self.heap) - 1) def pop(self): if not self.heap: return None top self.heap[0] last self.heap.pop() if self.heap: self.heap[0] last self._sift_down(0) return top def _sift_up(self, idx): parent (idx - 1) // 2 while idx 0 and self.heap[idx] self.heap[parent]: self.heap[idx], self.heap[parent] self.heap[parent], self.heap[idx] idx parent parent (idx - 1) // 2 def _sift_down(self, idx): n len(self.heap) while True: left 2 * idx 1 right 2 * idx 2 smallest idx if left n and self.heap[left] self.heap[smallest]: smallest left if right n and self.heap[right] self.heap[smallest]: smallest right if smallest idx: break self.heap[idx], self.heap[smallest] self.heap[smallest], self.heap[idx] idx smallest這個類里最值得研究的是sift_down。每次需要比較左孩子和右孩子找出更小的那一個然后交換。如果忽略了其中一側(cè)越界條件代碼會在訪問self.heap[right]等位置時拋IndexError。此外在pop方法里把最后一個元素移到堆頂再下沉這是保持完全二叉樹結(jié)構(gòu)的關(guān)鍵技巧不要圖省事直接把兩個孩子中較小的那個頂上根節(jié)點(diǎn)那樣數(shù)組里會出現(xiàn)空洞堆的結(jié)構(gòu)就錯了。4.3 自定義優(yōu)先隊(duì)列不要讓“不可比較”背鍋很多時候要放進(jìn)堆里的不是整數(shù)而是一個任務(wù)對象需要按某個字段排序。直接使用heapq時堆內(nèi)部要比較兩個元素的大小。如果對象沒有實(shí)現(xiàn)比較方法Python會拋TypeError not supported between instances of Task and Task。解法之一是給類實(shí)現(xiàn)__lt__方法告訴堆“先后順序如何比較”。例如class Task: def __init__(self, priority, name): self.priority priority self.name name def __lt__(self, other): return self.priority other.priority更常見的做法是往堆里插入(priority, counter, task)三元組。注意不要只插入(priority, task)因?yàn)楫?dāng)兩個任務(wù)優(yōu)先級相同時Python會繼續(xù)比較第二個元素task如果task對象不比大小又會報(bào)錯。加一個自增的counter可以保證所有優(yōu)先級相同的情況下按照入堆先后排序同時不會觸發(fā)task之間的比較。這種處理方式在Java里也有對應(yīng)版本Java的PriorityQueue需要傳入Comparator否則要求元素實(shí)現(xiàn)Comparable。定義一個比較器時同樣要注意優(yōu)先級相同的情況否則兩個優(yōu)先級一致的任務(wù)會導(dǎo)致隊(duì)列內(nèi)部比較分不出勝負(fù)雖然不一定報(bào)錯但順序會不符合預(yù)期。4.4 大數(shù)據(jù)量場景下的TopK堆的經(jīng)典主場假設(shè)你有一個大文件里面每一行是一個字符串需要找出出現(xiàn)次數(shù)最多的前100個字符串。如果文件不大你可以用Counter統(tǒng)計(jì)完直接排序但如果是幾十GB的日志把所有統(tǒng)計(jì)結(jié)果排序不僅慢而且沒必要。這時堆就能派上用場。思路是先用哈希表統(tǒng)計(jì)每個字符串出現(xiàn)的次數(shù)然后維護(hù)一個大小為K的小頂堆遍歷哈希表的過程中如果堆中元素不足K個直接入堆如果當(dāng)前字符串次數(shù)大于堆頂元素的次數(shù)把堆頂替換掉。為什么找最大K個要用小頂堆而不是大頂堆因?yàn)樾№敹训亩秧斒钱?dāng)前“前K大”里的最小值一旦來了更大的數(shù)就可以馬上淘汰掉最小值如果用大頂堆堆頂是當(dāng)前前K大中的最大值新元素永遠(yuǎn)比不過堆頂就沒有任何元素能被淘汰堆里存的反而是所有元素里最小的K個思路正好反了。示例代碼import heapq def top_k_frequent(words, k): # 這里省略 words 的統(tǒng)計(jì)邏輯假設(shè) counts 是 dict counts {} for word in words: counts[word] counts.get(word, 0) 1 heap [] for word, cnt in counts.items(): if len(heap) k: heapq.heappush(heap, (cnt, word)) elif cnt heap[0][0]: heapq.heapreplace(heap, (cnt, word)) # 堆頂在前需要逆序得到從大到小 result [] while heap: result.append(heapq.heappop(heap)[1]) result.reverse() return result最終內(nèi)存占用只和K有關(guān)在K遠(yuǎn)小于數(shù)據(jù)總量時這是一個非常省內(nèi)存的方案。實(shí)際在海量日志中統(tǒng)計(jì)Top IP、Top接口錯誤碼都可以把這個思路封裝成一個通用函數(shù)配合逐行讀取大文件使用。5. 避坑指南常見誤區(qū)和排查經(jīng)驗(yàn)5.1 關(guān)于堆的高頻疑問速查表疑問答案堆的插入/刪除復(fù)雜度是多少O(log n)其中n為堆中元素個數(shù)建堆復(fù)雜度是多少O(n)用從最后一個非葉子節(jié)點(diǎn)往前不斷下沉的方法堆排序是穩(wěn)定排序嗎不是堆排序在交換過程中會改變相同元素的相對順序找前K個最大元素用大頂堆還是小頂堆用小頂堆維持大小為K的堆堆頂是前K個中的最小值Python heapq默認(rèn)是什么堆小頂堆每次pop得到最小值需要大頂堆時就存相反數(shù)C priority_queue默認(rèn)是什么堆大頂堆需要傳greater 來改成小頂堆Java的PriorityQueue默認(rèn)是什么堆小頂堆可通過Comparator改成大頂堆棧溢出一般是什么原因無限遞歸、過大的局部變量、創(chuàng)建了過大的棧上數(shù)組Java堆報(bào)OutOfMemoryError怎么定位看GC日志、導(dǎo)出堆快照用MAT分析別盲目加-Xmx堆外內(nèi)存報(bào)OOM怎么排查檢查MaxDirectMemorySize設(shè)置、用VM.native_memory查native內(nèi)存占用5.2 如何一眼判斷是棧問題還是堆問題在實(shí)踐中判斷錯誤類型比盲目修復(fù)更重要。下面是幾種常見報(bào)錯信息和對應(yīng)的排查方向如果你的C/C程序崩潰并且日志里有“stack overflow”字樣說明大概率是棧溢出先去看遞歸有沒有退出條件再看局部變量是否聲明了一個巨大的數(shù)組。?？臻g有限一般只有幾MB把一個10MB的數(shù)組放在main函數(shù)里也會直接爆棧。Java出現(xiàn)StackOverflowError時同理先往遞歸方向查出現(xiàn)OutOfMemoryError: Java heap space的時候才需要去調(diào)堆相關(guān)參數(shù)和找內(nèi)存泄漏對象。Python里的RecursionError并不是全部因?yàn)檫f歸過深有時是遞歸函數(shù)忘記寫終止條件有時只是代碼本來需要的遞歸深度超過了Python默認(rèn)的遞歸限制?？梢杂胹ys.setrecursionlimit調(diào)高但根因還是要改算法或增加退出條件。如果你遇到的是“編譯器堆空間不足”這類報(bào)錯先別懷疑你寫的代碼有問題。CC編譯器或JIT編譯器在編譯過程中自身也需要內(nèi)存當(dāng)機(jī)器物理內(nèi)存不足或者并行編譯任務(wù)開太多時同樣會報(bào)內(nèi)存不夠。降低優(yōu)化級別、減少并行編譯任務(wù)、關(guān)閉無關(guān)應(yīng)用釋放內(nèi)存是最常見的緩解方式。5.3 一些“過來人”的體會和建議最后分享幾個我自己經(jīng)歷過的實(shí)際經(jīng)驗(yàn)。有一段時間我在做日志分析工具數(shù)據(jù)量大到直接用sort排完再取Top結(jié)果會占掉太多內(nèi)存換成堆以后不管輸入文件多大進(jìn)程內(nèi)存都穩(wěn)定在幾十MB以內(nèi)。這種“只保留最關(guān)心的K個其余邊來邊丟”的思路極其適合流式處理的場景建議大家真正跑一遍。還有一次在線上的業(yè)務(wù)代碼里看到有人為了取出數(shù)組中最大的10個數(shù)先把整個數(shù)組排序再切片完全沒必要。對幾千個數(shù)排序也許感知不到差異但如果這個操作出現(xiàn)在高頻接口路徑里一次排序可能是O(n log n)而用堆只要O(n log k)。能明顯降低CPU開銷。算法題里刷過很多次堆工作里卻忘了用它挺常見的。我自己的學(xué)習(xí)方法向來是“兩條腿走路”數(shù)據(jù)結(jié)構(gòu)堆靠算法題找手感內(nèi)存堆靠線上事故攢經(jīng)驗(yàn)。兩邊都經(jīng)歷一遍后你自然就會形成一套判斷力——看到“堆”字先反問一句這里討論的是執(zhí)行邏輯里的優(yōu)先隊(duì)列還是內(nèi)存區(qū)域里的動態(tài)分配還是IO層里的直接內(nèi)存這個能力比背再多概念都管用建議你也試試。