堆的完整實現

GitHub地址

有夢想的電信狗

前言

堆（Heap）是一種特殊的完全二叉樹數據結構，常用于實現優先級隊列。本文基于C語言實現大跟堆，包含核心操作：插入元素、刪除堆頂元素、堆化操作等。以下是完整實現及詳細解析。

---

堆的核心功能實現

重溫堆的定義

普通的二叉樹是不適合用數組來存儲的，因為可能會存在大量的空間浪費。而完全二叉樹更適合使用順序結構存儲。

現實中我們通常把堆(一種特殊的二叉樹)使用順序結構的數組來存儲。

需要注意的是這里的堆和操作系統虛擬進程地址空間中的堆是兩回事，一個是數據結構，一個是操作系統中管理內存的一塊區域分段

二叉樹的順序存儲，是堆的前身

在順序存儲的二叉樹上加一些限定條件，定義為堆

• 小根堆 : 樹中所有父結點都小于或等于子節點
• 大根堆 樹中所有父結點都大于或等于子節點
• 堆可以用來排序，但堆并非是有序的！

堆的性質：

• 堆中某個節點的值總是不大于或不小于其父節點的值；
• 堆總是一棵完全二叉樹。

堆結構定義

//實現大堆   這里以實現大根堆為例子
typedef int HeapDataType;	//定義堆中存放的數據類型，方便修改
typedef struct HeapNode {HeapDataType* base;   // 堆存儲數組基地址int size;              // 當前元素個數int capacity;          // 堆容量
}Heap;

結構說明：

• base：動態數組基地址，用于存儲堆元素，用數組來順序存儲
• size：當前堆中元素數量
• capacity：數組總容量

數組存儲的二叉樹的下標特性：

• parent = (child - 1) / 2
• lefichild = parent * 2 + 1
• lefichild = parent * 2 + 2

功能一覽：

//堆初始化與銷毀
void HeapInit(Heap* pheap);
void HeapDestroy(Heap* pheap);//堆插入和刪除
void HeapPush(Heap* pheap, HeapDataType data);
void HeapPop(Heap* pheap);
//堆的向上 向下調整
void AdjustUp(HeapDataType* arr, int child);
void AdjustDown(HeapDataType* arr, int size, int parent);//交換堆中的元素
void Swap(HeapDataType* left, HeapDataType* right);
//獲取堆頂元素
HeapDataType HeapTop(Heap* pheap);
//判斷堆是否為空
bool HeapEmpty(Heap* pheap);
//獲取堆的size
int HeapSize(Heap* pheap);

---

1. 堆初始化與銷毀

初始化：

//堆初始化
void HeapInit(Heap* pheap) {assert(pheap);	pheap->base = (HeapDataType*)malloc(sizeof(HeapDataType) * 4);if (pheap->base == NULL) {perror("malloc failed\n");return;}pheap->size = 0;pheap->capacity = 4;
}

實現思路：

• 斷言指針有效性，堆結構指針必須存在
• 為堆分配初始容量（暫設置為4個元素空間），申請空間失敗時報錯并返回

• 初始化size為0表示空堆，capacity初始化為申請的空間
• 時間復雜度：O(1)

注意事項：

• 必須進行指針有效性斷言檢查
• 初始容量不宜過小（建議為4的倍數）

銷毀：

//清理資源
void HeapDestroy(Heap* pheap) {assert(pheap);free(pheap->base);pheap->base = NULL;pheap->capacity = pheap->size = 0;
}

實現思路：

• assert斷言堆結構指針不為空
• free釋放動態分配的存儲空間

• 將指針置NULL防止野指針
• 將size和capacity都置為0
• 時間復雜度：O(1)

---

2. 元素交換函數

void Swap(HeapDataType* child, HeapDataType* parent) {HeapDataType temp = *child;*child = *parent;*parent = temp;
}

功能：交換父子節點數值
使用場景：堆化（向上調整/向下調整）時的元素位置調整

交換函數功能較為簡單，此處不過多贅述。

---

3. 堆化操作

向上調整 或向下調整的條件是，左右子樹 必須是 大堆 或者 小堆

向上調整（子→父）

// 插入數據向上調整， 刪除數據向下調整
//向上調整 或向下調整的條件是，左右子樹 必須是大堆 或者 小堆
void AdjustUp(HeapDataType* arr, int child) {	//child是需要調整的節點的下標assert(arr);int parent = (child - 1) / 2;//while (parent >= 0) {		//	 個人建議while的循環條件內不要寫太復雜的條件//寫成  child > 0  會更好  因為 最壞時 child 為 0 ，此時parent = (child-1)/2  也為0//因此 實際上 parent 不會為 <= 0while (child > 0) {   // child 等于 0 或小于 0 時就不用再調整了if (arr[child] > arr[parent]) {Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}//child <= parent 時else	break;}
}

功能：將新插入堆的元素調整到合適位置 ，使其滿足堆的性質

• child是新插入元素的下標，一般是size-1（即通過尾插進入的最后一個元素的下標）
• arr是待調整的數組指針，斷言arr非空
• child 為子節點，向上調整思路：
  • 通過parent = (child - 1) / 2，計算待調整結點的父節點的下標
  • child下標為0時，代表最后一次交換(調整)已結束。因此循環結束條件為child == 0
  • 比較父子結點的大小，子節點大于父節點時，交換，滿足大根堆的邏輯，同時下標child和parent進行更新
  • 當前child結點 < parent結點時，代表以滿足大根堆，直接結束循環即可。
• 時間復雜度為 O(logN)

終止條件：

• 以下條件滿足其一，循環即可終止。
  • 子節點值 ≤ 父節點值
  • 到達堆頂（child=0）

向下調整（父→子）

// 向下調整 到葉子結點結束，葉子結點的左孩子 的下標  大于 size   size是數組的大小
void AdjustDown(HeapDataType* arr, int size, int parent) {assert(arr);assert(parent >= 0 && parent < size);	//parent非負 且 不能越界int child = parent * 2 + 1;while (child < size) {//檢查 child+1 是否越界 以及 找出左右孩子中更大的那個//child + 1 >= size 時，表示當前父節點只有左孩子if (child + 1 < size && arr[child + 1] > arr[child])++child;if (arr[child] > arr[parent]) {Swap(&arr[parent], &arr[child]);parent = child;child = parent * 2 + 1;}elsebreak;}
}

實現思路：

• 斷言arr和parent >= 0 && parent < size，保證arr存在，parent非負且不越界
  • parent一般是0，從堆頂元素開始調整，盡可能地保持了堆的結構。
• child = parent * 2 + 1：計算左孩子的下標，右孩子的下標是左孩子下標+1
• child >= size時，代表最后一個元素已完成交換，循環結束
• 檢查child+1是否越界以及 找出左右孩子中更大的那個，讓較大者與parent結點進行比較。
• child更大時，與parent結點進行交換，child和parent接著移動。

實現要點：

1. 總是與較大的子節點比較
2. 循環終止條件（滿足其一即終止）：
   • parent數據 ≥ 兩個child節點數據，此時已符合大根堆的條件，向下調整完成
   • child > size時，所有的節點已完成交換，此時已符合大根堆的條件，向下調整完成

時間復雜度為 O(logN)

小根堆的調整：可與大根堆類比

---

4. 堆元素插入

• 向上調整的過程

// 插入，不能指定位置插入。
// 因為新元素插入后要進行調整使其滿足堆的結構，指定的位置不一定是最終調整后的位置
void HeapPush(Heap* pheap, HeapDataType data) {assert(pheap);	//空堆也可以push，但需保證結構體存在//插入檢查是否需要擴容if (pheap->size == pheap->capacity) {HeapDataType* newSpace = (HeapDataType*)realloc(pheap->base, sizeof(HeapDataType) * pheap->capacity * 2);if (newSpace == NULL) {perror("realloc failed\n");return;}pheap->base = newSpace;pheap->capacity *= 2;}//更新pheap->base[pheap->size] = data;pheap->size++;//插入后需向上調整，保證插入后滿足堆的特性AdjustUp(pheap->base, pheap->size - 1);	//size++ 后，size-1 是新插入元素的下標
}

實現思路：

1. 斷言堆存在檢查并擴容（2倍擴容策略）
   • 擴容：
     • 開空間，二倍擴容
     • 判斷是否開辟成功
     • 更改指針和容積
2. 將新元素插入數組末尾，更新size，盡可能的保持原來堆的結構。
3. 執行向上調整操作維護堆結構

時間復雜度：

• 最優：O(logN)（不需要擴容）
• 最差：O(N)（觸發擴容）

---

5. 堆元素刪除

• 向下調整的過程

//堆的刪除  應當刪除堆頂的元素，刪除堆尾的數據沒有意義。
//刪除最大的或最小的，可以選出第二大或第二小的
//挪動刪除(直接刪)的缺點:  1. 效率低下O(n)   2.  堆的父子關系全亂了
// 刪堆頂的元素，將第一個元素和最后一個元素交換(最大限度的保持了原有的關系)，再向下調整維持堆的大小關系
void HeapPop(Heap* pheap) {assert(pheap && pheap->size > 0);assert(!HeapEmpty(pheap));//刪除堆頂元素   交換堆頂元素 和 堆尾元素Swap(&pheap->base[0], &pheap->base[pheap->size - 1]);pheap->size--;		//刪除數據，讓size-1   size--之后，可能會為0// 僅當堆非空時進行向下調整if (pheap->size > 0) {AdjustDown(pheap->base, pheap->size, 0);}
}

實現思路：

• 斷言堆存在并且確保堆為非空。
• 通過交換堆頂元素和堆尾元素，并更改size--來實現數組內元素的刪除
• 通過size--的方式刪除元素，向下調整時，要確保size的值不為0

注意事項：

• 刪除前必須檢查堆是否為空
• size減至0時無需向下調整操作

---

6. 輔助功能函數

堆的判空

//判斷堆是否為空
bool HeapEmpty(Heap* pheap) {assert(pheap);return pheap->size == 0;
}

獲取堆頂元素

//獲取堆頂元素
HeapDataType HeapTop(Heap* pheap) {assert(pheap);assert(pheap->base);return pheap->base[0];
}

• 0號元素就是堆頂元素

獲取堆的大小

//獲取堆的size
int HeapSize(Heap* pheap) {assert(pheap);return pheap->size;
}

功能說明：

• HeapTop：獲取堆頂元素（極值）
  • 大根堆時是極大值
  • 小跟堆時是極小值
• HeapEmpty：判斷堆是否為空
• HeapSize：獲取當前元素個數

---

結語

本文完整實現了基于數組存儲的大根堆結構，重點闡釋了堆化過程中向上調整與向下調整的核心邏輯。通過動態數組管理、二倍擴容策略及父子節點下標計算，構建了插入元素時末尾上浮、刪除堆頂時首尾交換后根節點下沉的高效操作，確保堆性質在O(logN)時間內得以維護。關鍵點在于理解完全二叉樹順序存儲的特性，以及插入/刪除時通過逐層比較交換維護父節點≥子節點的規則。實際應用中可調整比較邏輯切換大小堆，適用于優先隊列、堆排序等場景，注意邊界處理避免空堆刪除和擴容失敗問題。

分享到此結束啦
一鍵三連，好運連連！