寫在前面上一篇 數(shù)據(jù)結(jié)構(gòu)-二叉樹一樹的基礎(chǔ)概念與二叉樹核心結(jié)構(gòu)-CSDN博客 我們學習了樹、二叉樹以及完全二叉樹并得到數(shù)組存儲下父子下標公式左孩子left parent * 2 1右孩子right parent * 2 2父節(jié)點parent (child - 1) / 2堆就是建立在完全二叉樹之上的數(shù)據(jù)結(jié)構(gòu)它把樹形邏輯映射到連續(xù)數(shù)組高效維護集合的最大值/最小值。堆不只是課堂考點工程中大量使用堆排序、Top?K問題、優(yōu)先級隊列、操作系統(tǒng)任務(wù)調(diào)度、Dijkstra最短路徑算法都離不開它。本文基于C語言完整實現(xiàn)0下標二叉堆講解Heap結(jié)構(gòu)體設(shè)計為什么傳結(jié)構(gòu)體指針向上調(diào)整、向下調(diào)整核心邏輯與易錯坑向上建堆 vs 向下建堆時間復(fù)雜度對比大小根堆切換方法堆排序原理搞懂「降序建小堆升序建大堆」排序算法橫向?qū)Ρ榷嘟M測試用例解讀與常見踩坑。代碼倉庫數(shù)據(jù)結(jié)構(gòu)/Heap · Luminous/Code_2026 - 碼云 - 開源中國一、什么是堆Heap堆是特殊的完全二叉樹只約束父子節(jié)點的大小關(guān)系整棵樹并不全局有序這點是絕大多數(shù)初學者的誤區(qū)。小根堆任意父節(jié)點的值 ≤ 子節(jié)點的值堆頂根一定是整個集合最小值。7 / \ 12 45 / \ 89 23底層數(shù)組{7,12,45,89,23}大根堆任意父節(jié)點的值 ≥ 子節(jié)點的值堆頂根一定是整個集合最大值。89 / \ 45 56 / 23特別注意堆不是有序數(shù)組。示例1 / \ 5 3 / 8滿足小根堆性質(zhì)但數(shù)組{1,5,3,8}并不是升序。堆只保證父子關(guān)系不保證左右子樹、兄弟節(jié)點之間有序。堆的優(yōu)勢(O(1))拿到極值想要整體有序需要堆排序。二、堆的存儲與結(jié)構(gòu)體設(shè)計邏輯上是完全二叉樹但不使用鏈式TreeNode節(jié)點。完全二叉樹幾乎沒有空間浪費直接用一段連續(xù)動態(tài)數(shù)組存儲效率更高。typedef int HPDataType; typedef struct Heap { HPDataType* a; // 動態(tài)數(shù)組存放堆元素 int size; // 當前有效元素個數(shù) int capacity; // 數(shù)組總?cè)萘?}Heap;a動態(tài)開辟的數(shù)組也可以直接掛載外部已有數(shù)組實現(xiàn)原地建堆size堆的有效元素[0,size?1]為有效區(qū)間capacity數(shù)組總?cè)萘坑糜谂袛嗍欠裥枰猺ealloc擴容。內(nèi)存示意capacity8size5[7][12][45][89][23][ ][ ][ ]三、接口為什么傳Heap*指針不傳Heap值拷貝函數(shù)原型對比// 傳值操作副本外面堆不會變化 void HeapPush(Heap hp, int x); // 傳指針操作原堆對象 void HeapPush(Heap* hp, int x);三點設(shè)計原因修改原堆對象插入、刪除會修改size、a指針。傳值會生成結(jié)構(gòu)體副本函數(shù)內(nèi)部修改全部作用在副本上外部堆完全不受影響邏輯失效。減少拷貝開銷雖然結(jié)構(gòu)體本身不大但傳值會完整復(fù)制結(jié)構(gòu)體傳指針只傳遞地址開銷恒定。核心支持外部數(shù)組復(fù)用原地建堆這是HeapCreate接口設(shè)計的關(guān)鍵?？梢灾苯影淹獠科胀〝?shù)組掛載到hp-a不需要malloc新空間、不需要拷貝數(shù)據(jù)。int arr[] {12,45,7,89,23,56}; HeapCreate(hp, arr, 6); // hp-a直接指向arr原地建堆省去內(nèi)存分配與拷貝也是堆排序可以做到(O(1))額外空間的底層思想。四、堆調(diào)整核心思想為什么需要向上和向下調(diào)整堆的本質(zhì)要求任意節(jié)點都必須滿足父節(jié)點和孩子節(jié)點之間的大小關(guān)系。以小根堆為例父節(jié)點 ↓ 父 ≤ 子 7 / \ 12 45但是在實際操作過程中插入元素只能破壞從新增節(jié)點到根節(jié)點這一條路徑刪除堆頂只能破壞從根節(jié)點到葉子節(jié)點這一條路徑因此沒有必要重新遍歷整棵樹只需要沿著一條路徑調(diào)整即可。這就是堆高效的原因利用完全二叉樹高度為 log N 的特點只需要調(diào)整一條路徑。4.1 向上調(diào)整新元素插入后的維護使用場景HeapPush插入元素例如當前小根堆10 / \ 20 30 / 40數(shù)組[10,20,30,40]現(xiàn)在插入新元素5。 按照完全二叉樹規(guī)則新元素只能接在末尾10 / \ 20 30 / \ 40 5對應(yīng)數(shù)組[10,20,30,40,5]此時發(fā)現(xiàn)5 20破壞小根堆性質(zhì)10 / \ 20 30 / 40 / 5所以需要讓新元素不斷向上移動。向上調(diào)整過程第一次交換10 / \ 5 30 / 40 / 20繼續(xù)比較5 10繼續(xù)交換5 / \ 10 30 / 40 / 20最終恢復(fù)小根堆5 / \ 10 30 / 40 / 20向上調(diào)整代碼對應(yīng)邏輯while(child 0) { parent(child-1)/2; if(a[child] a[parent]) { Swap(a[child],a[parent]); childparent; } else { break; } }核心邏輯孩子違反規(guī)則 ↓ 和父節(jié)點交換 ↓ 繼續(xù)向上檢查插入只能影響新增節(jié)點到根節(jié)點路徑因此使用向上調(diào)整。時間復(fù)雜度 樹高度 h log N最壞一路交換到根單次調(diào)整 O(log N)。4.2 向下調(diào)整刪除堆頂后的維護使用場景HeapPop刪除堆頂例如小根堆5 / \ 10 20 / \ 30 40數(shù)組[5,10,20,30,40]如果直接刪除堆頂元素5樹形結(jié)構(gòu)直接殘缺? / \ 10 20 / 30完全二叉樹結(jié)構(gòu)被破壞不能直接刪除根。正確操作分為兩步第一步交換堆頂和最后元素交換5 ? 4040 / \ 10 20 / 30數(shù)組變?yōu)閇40,10,20,30]此時樹形結(jié)構(gòu)完整但堆性質(zhì)被破壞。第二步讓40向下移動左右孩子比較10 20選擇更小的孩子10。 交換父與子10 / \ 40 20 / 30繼續(xù)比較40 30再次交換10 / \ 30 20 / 40堆性質(zhì)恢復(fù)。向下調(diào)整代碼思想child parent*21; while(childsize) { //找到更優(yōu)孩子 //父子比較 //交換 parentchild; }核心邏輯父節(jié)點違反規(guī)則 ↓ 選擇更小/更大的孩子 ↓ 交換 ↓ 繼續(xù)向下刪除堆頂只影響根節(jié)點到葉子的路徑所以使用向下調(diào)整。時間復(fù)雜度O(log N)五、堆基礎(chǔ)接口實現(xiàn)初始化、銷毀void HeapInit(Heap* hp) { assert(hp); hp-a NULL; hp-size 0; hp-capacity 0; } void HeapDestory(Heap* hp) { assert(hp); free(hp-a); hp-a NULL; hp-capacity hp-size 0; }特別注意HeapCreate掛載棧數(shù)組時棧內(nèi)存不能free銷毀前務(wù)必手動置空hp-a NULL否則程序崩潰。堆插入 HeapPush尾插元素容量不足則二倍realloc擴容新元素做向上調(diào)整。單次插入(O(\log N))。void HeapPush(Heap* hp, HPDataType x) { if (hp-capacity hp-size) { int num hp-capacity 0 ? 4 : hp-capacity * 2; HPDataType* tmp (HPDataType*)realloc(hp-a, sizeof(HPDataType) * num); if (tmp NULL) { perror(realloc fail); exit(-1); } hp-a tmp; hp-capacity num; } hp-a[hp-size] x; hp-size; HeapAdjustUp(hp-a, hp-size-1); }刪除堆頂 HeapPop不能直接刪除數(shù)組下標0會破壞完全二叉樹結(jié)構(gòu)。正確流程堆頂與末尾元素交換 → size?1邏輯刪除末尾 → 對根做向下調(diào)整。單次刪除(O(log N))。void HeapPop(Heap* hp) { assert(hp); assert(hp-size 0); Swap(hp-a[0], hp-a[hp-size-1]); hp-size--; HeapAdjustDown(hp-a, hp-size, 0); }取堆頂、判空HPDataType HeapTop(Heap* hp) { assert(hp); assert(hp-size 0); return hp-a[0]; } bool HeapEmpty(Heap* hp) { assert(hp); return hp-size 0; }六、兩種建堆方式詳細對比如果現(xiàn)在給你一個無序數(shù)組int a[]{12,45,7,89,23,56};如何把它構(gòu)建成堆存在兩種實現(xiàn)思路。6.1 方法一向上調(diào)整建堆思想假設(shè)前面的元素已經(jīng)是堆不斷插入新元素。推演過程初始12加入4512 \ 45滿足堆性質(zhì)。加入7數(shù)組[12,45,7]12 / \ 45 77 12違反小根堆進行交換7 / \ 45 12繼續(xù)加入897 / \ 45 12 / 89繼續(xù)加入237 / \ 23 12 / \ 89 45最終形成小根堆7 / \ 23 12 / \ 89 45對應(yīng)代碼for(int i1;in;i) { HeapAdjustUp(a,i); }每新增一個元素就做一次向上調(diào)整單次最多 log N。 總時間復(fù)雜度O(N logN)。6.2 方法二向下調(diào)整建堆推薦思想葉子節(jié)點天然滿足堆只需要調(diào)整非葉子節(jié)點。數(shù)組12 45 7 89 23 56對應(yīng)完全二叉樹12 / \ 45 7 / \ / 89 23 56葉子節(jié)點89、23、56葉子不需要調(diào)整。從最后一個非葉子節(jié)點向前處理。 最后非葉子節(jié)點下標(n?2)/2本例(6?2)/2 2。1處理下標2節(jié)點7 / 56滿足堆無需交換。2處理下標1節(jié)點45 / \ 89 23孩子23更小執(zhí)行交換23 / \ 89 453處理下標0節(jié)點12 / \ 23 7 / \ / 89 45 56孩子7最小執(zhí)行交換7 / \ 23 12 / \ / 89 45 56小根堆建立完成。為什么向下建堆是 (O(N))很多人直覺認為每個節(jié)點調(diào)整代價 log N總復(fù)雜度就是 O(N log N)這個理解是錯誤的。原因在于不同層節(jié)點數(shù)量、調(diào)整次數(shù)不一樣底層節(jié)點數(shù)量最多但高度為0幾乎不用向下調(diào)整越靠近上層節(jié)點數(shù)量越少但向下調(diào)整步數(shù)變多。求和拿到完整數(shù)組時優(yōu)先選擇向下調(diào)整建堆。建堆方式最終總結(jié)方式核心思想復(fù)雜度適用場景向上建堆模擬不斷Push插入O(N log N)動態(tài)逐個插入元素向下建堆從最后非葉子節(jié)點向前調(diào)整(O(N))已有完整數(shù)組原地建堆七、堆排序深度解析重點區(qū)分建堆O(N)完整堆排序整體(O(N logN))。堆排序分為兩步將無序數(shù)組建堆不斷把堆頂極值交換到數(shù)組尾部尾部區(qū)間逐步有序前面區(qū)間繼續(xù)向下調(diào)整維護堆。void HeapSort(int* a, int n) { // 降序建小堆 // 升序建大堆 //for (int i 1; i n; i)//向上調(diào)整 O(N*logN) //{ // HeapAdjustUp(a, i); //} //向下調(diào)整建堆 O(N) for (int i (n - 1 - 1) / 2; i 0; i--) { HeapAdjustDown(a, n, i); } int end n - 1; while (end 0) { Swap(a[0], a[end]); HeapAdjustDown(a, end, 0); --end; } }核心口訣降序建小堆升序建大堆很多同學在這里記反推導(dǎo)邏輯 堆頂永遠是當前區(qū)間的極值每次把堆頂交換到數(shù)組末尾末尾位置就排好序不再參與后續(xù)堆調(diào)整。建小根堆堆頂是最小值。最小值不斷放到數(shù)組末尾尾部依次存放最小、次小……最終整體數(shù)組降序。建大根堆堆頂是最大值。最大值不斷放到數(shù)組末尾尾部依次存放最大、次大……最終整體數(shù)組升序。復(fù)雜度拆解建堆階段O(N)while循環(huán)執(zhí)行n?1次每次向下調(diào)整(O(log N))(O(N log N))總復(fù)雜度 TO(N)O(N log N)O(N log N)大O表示法保留高階項。空間復(fù)雜度(O(1)) 原地排序穩(wěn)定性不穩(wěn)定排序。八、排序算法橫向?qū)Ρ人惴ㄆ骄鶗r間最壞時間額外空間穩(wěn)定性評價冒泡排序O(N^2)O(N^2)(O(1))穩(wěn)定僅教學大數(shù)據(jù)量性能極差堆排序O(N log N)O(N log N)(O(1))不穩(wěn)定最壞情況性能穩(wěn)定內(nèi)存友好緩存局部性較差快速排序O(N log N)O(N^2)O(log N)遞歸棧不穩(wěn)定實際運行最快語言內(nèi)置排序核心常數(shù)因子小堆排序最壞時間不會退化但實際跑的速度一般弱于快排。堆真正強項不是完整排序而是Top?K、優(yōu)先級隊列場景。Top?K簡單理解海量數(shù)據(jù)求前K大元素不需要全部排序。維護大小為K的堆復(fù)雜度O(N log K)K遠小于N的時候比全局排序O(N log N)效率高很多。九、項目代碼結(jié)構(gòu)與test.c測試解讀項目三層文件拆分Heap.h結(jié)構(gòu)體、函數(shù)聲明Swap為內(nèi)部輔助函數(shù)不對外暴露Heap.c全部接口實現(xiàn)默認小根堆test.c三組測試同一時間只啟用一組main其余注釋。測試1裸數(shù)組原地堆排序求前K大元素當前啟用直接操作普通數(shù)組不使用Heap結(jié)構(gòu)體原地完成堆排序排序完成數(shù)組降序數(shù)組前k個即為前k大元素。注釋保留向上調(diào)整建堆代碼用于對比學習。測試2堆接口Push/Pop整套功能測試完整驗證初始化、插入、彈出、堆頂、判空、銷毀。當前是小根堆彈出順序從小到大切換大根堆后輸出會改變。測試3拷貝堆數(shù)組不破壞原堆求前k大malloc復(fù)制一份堆內(nèi)存在副本上執(zhí)行Pop取TopK原始堆數(shù)據(jù)不受影響。注意tmpHp只是借用malloc出來的內(nèi)存不要調(diào)用HeapDestory(tmpHp)手動free拷貝內(nèi)存即可避免二次釋放。代碼倉庫已經(jīng)上傳本篇及以往博客代碼可以拉取代碼學習使用。數(shù)據(jù)結(jié)構(gòu)/Heap · Luminous/Code_2026 - 碼云 - 開源中國十、常見坑點匯總0下標堆父子公式不要和1下標混用混用直接邏輯錯亂大小根堆三處比較符號必須同步修改否則堆性質(zhì)失效HeapCreate掛載棧數(shù)組銷毀前hp-a NULL禁止free棧內(nèi)存Pop不能直接刪除下標0必須交換堆頂與末尾元素再向下調(diào)整已有完整數(shù)組建堆優(yōu)先向下調(diào)整建堆O(N)不要向上調(diào)整區(qū)分概念建堆O(N)堆排序整體(O(N logN))不要混淆兩個復(fù)雜度。寫在最后從樹形結(jié)構(gòu)到數(shù)組存儲從堆調(diào)整到堆排序二叉堆看似只是完全二叉樹的一種特殊形式但背后體現(xiàn)的是數(shù)據(jù)結(jié)構(gòu)中非常重要的思想利用結(jié)構(gòu)特點降低操作成本。本篇重點掌握了幾個核心堆本質(zhì)是完全二叉樹通過數(shù)組實現(xiàn)避免了鏈式結(jié)構(gòu)的額外空間開銷向上調(diào)整解決「插入后維護堆性質(zhì)」的問題向下調(diào)整解決「刪除堆頂以及建堆」的問題已有完整數(shù)組時優(yōu)先使用向下調(diào)整建堆時間復(fù)雜度從 (O(N logN)) 優(yōu)化到 (O(N))堆排序雖然實際效率通常不如快速排序但它擁有穩(wěn)定的最壞情況復(fù)雜度和 (O(1)) 空間優(yōu)勢堆真正強大的地方并不是排序而是在動態(tài)維護極值例如 Top-K、優(yōu)先級隊列、任務(wù)調(diào)度等場景。學習數(shù)據(jù)結(jié)構(gòu)時不應(yīng)該只停留在記憶代碼和復(fù)雜度更重要的是理解每個設(shè)計背后的原因為什么完全二叉樹適合數(shù)組存儲為什么插入使用向上調(diào)整刪除使用向下調(diào)整為什么建堆推薦從最后一個非葉子節(jié)點開始為什么堆排序選擇大根堆或小根堆會影響最終排序方向當這些問題真正理解后堆就不再是一段需要背誦的代碼而會成為解決實際問題的一種工具。下一篇將繼續(xù)深入二叉樹專題學習二叉樹的遍歷、遞歸思想以及更多經(jīng)典應(yīng)用。從基礎(chǔ)結(jié)構(gòu)出發(fā)逐步構(gòu)建數(shù)據(jù)結(jié)構(gòu)與算法能力體系。