什么是堆（Heap）？

堆是一種特殊的樹形數據結構，它滿足以下兩個主要屬性：

1. 結構性（完全二叉樹）：

   • 堆總是一個完全二叉樹 (Complete Binary Tree)。這意味著，除了最后一層，所有的層都是完全填充的，并且最后一層的所有節點都盡可能地向左填充。

   • 這個特性使得堆非常適合用數組來表示，因為節點之間的父子關系可以通過索引輕松計算。

2. 堆序性（Heap Property）：

   • 最大堆（Max-Heap）：?在一個最大堆中，每個父節點的值都大于或等于其子節點的值。這意味著，根節點是整個堆中的最大元素。

   • 最小堆（Min-Heap）：?在一個最小堆中，每個父節點的值都小于或等于其子節點的值。這意味著，根節點是整個堆中的最小元素。

總結：?堆是一個用數組實現的完全二叉樹，并且滿足特定的堆序性（父節點大于等于子節點或小于等于子節點）。

堆的ADT（抽象數據類型）操作

一個典型的堆通常支持以下操作：

1. createHeap(capacity): 創建一個指定容量的空堆。

2. isFull(heap): 檢查堆是否已滿。

3. isEmpty(heap): 檢查堆是否為空。

4. insert(heap, value): 將新元素插入堆中，并保持堆的性質。

5. deleteMax(heap)?/?deleteMin(heap): 刪除堆中最大/最小元素（通常是根節點），并保持堆的性質。

6. peekMax(heap)?/?peekMin(heap): 查看堆中最大/最小元素（根節點），但不刪除。

7. heapifyUp(heap, index): 向上調整堆，當子節點的值發生變化（通常是插入操作后）。

8. heapifyDown(heap, index): 向下調整堆，當父節點的值發生變化（通常是刪除操作或建堆操作后）。

9. buildHeap(array, size): 將一個無序數組轉換為一個堆。

堆的C語言實現原理（基于數組）

由于堆是完全二叉樹，它最常用的實現方式是使用數組。這種實現方式的優點在于：

• 空間效率高：?無需存儲指針。

• 計算效率高：?父子節點的關系可以通過簡單的算術運算得出。

對于一個基于0索引的數組?arr：

• 根節點：?arr[0]

• 節點?i?的左子節點：?arr[2 * i + 1]

• 節點?i?的右子節點：?arr[2 * i + 2]

• 節點?i?的父節點：?arr[(i - 1) / 2]?(注意整數除法)

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> // For bool type// -----------------------------------------------------------
// 1. 定義堆結構體
// -----------------------------------------------------------
typedef struct MaxHeap {int* arr;       // 存儲堆元素的數組int capacity;   // 堆的最大容量int size;       // 堆當前元素的數量
} MaxHeap;// -----------------------------------------------------------
// 2. 輔助函數
// -----------------------------------------------------------// 交換兩個整數的值
void swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp;
}// -----------------------------------------------------------
// 3. 核心堆操作函數
// -----------------------------------------------------------// 創建一個空的MaxHeap
MaxHeap* createMaxHeap(int capacity) {MaxHeap* newHeap = (MaxHeap*)malloc(sizeof(MaxHeap));if (newHeap == NULL) {perror("Failed to allocate memory for MaxHeap structure");exit(EXIT_FAILURE);}newHeap->arr = (int*)malloc(sizeof(int) * capacity);if (newHeap->arr == NULL) {perror("Failed to allocate memory for MaxHeap array");free(newHeap); // Clean up partially allocated memoryexit(EXIT_FAILURE);}newHeap->capacity = capacity;newHeap->size = 0;printf("MaxHeap created with capacity: %d\n", capacity);return newHeap;
}// 釋放堆占用的內存
void destroyMaxHeap(MaxHeap* heap) {if (heap != NULL) {free(heap->arr);heap->arr = NULL;free(heap);printf("MaxHeap destroyed.\n");}
}// 檢查堆是否為空
bool isEmpty(MaxHeap* heap) {return heap->size == 0;
}// 檢查堆是否已滿
bool isFull(MaxHeap* heap) {return heap->size == heap->capacity;
}// 獲取父節點的索引
int getParentIndex(int i) {return (i - 1) / 2;
}// 獲取左子節點的索引
int getLeftChildIndex(int i) {return 2 * i + 1;
}// 獲取右子節點的索引
int ietRightChildIndex(int i) {return 2 * i + 2;
}// 判斷給定索引是否具有左子節點
bool hasLeftChild(MaxHeap* heap, int i) {return getLeftChildIndex(i) < heap->size;
}// 判斷給定索引是否具有右子節點
bool hasRightChild(MaxHeap* heap, int i) {return ietRightChildIndex(i) < heap->size;
}/*** @brief 向上調整堆 (Heapify Up)* 當子節點的值大于父節點時，將其與父節點交換，直到滿足堆性質或到達根節點。* 通常在插入新元素后調用。** @param heap 指向MaxHeap的指針* @param index 待調整元素的當前索引*/
void heapifyUp(MaxHeap* heap, int index) {// 當當前節點不是根節點，且當前節點的值大于其父節點的值時while (index > 0 && heap->arr[getParentIndex(index)] < heap->arr[index]) {swap(&heap->arr[index], &heap->arr[getParentIndex(index)]);index = getParentIndex(index); // 移動到父節點的位置，繼續向上檢查}
}/*** @brief 向下調整堆 (Heapify Down)* 當父節點的值小于其子節點時，將其與最大的子節點交換，直到滿足堆性質或到達葉子節點。* 通常在刪除根元素或建堆時調用。** @param heap 指向MaxHeap的指針* @param index 待調整元素的當前索引*/
void heapifyDown(MaxHeap* heap, int index) {int maxIndex = index;int leftChild = getLeftChildIndex(index);int rightChild = ietRightChildIndex(index);// 檢查左子節點是否存在且大于當前最大值if (hasLeftChild(heap, index) && heap->arr[leftChild] > heap->arr[maxIndex]) {maxIndex = leftChild;}// 檢查右子節點是否存在且大于當前最大值if (hasRightChild(heap, index) && heap->arr[rightChild] > heap->arr[maxIndex]) {maxIndex = rightChild;}// 如果maxIndex不是當前index，說明子節點比父節點大，需要交換if (maxIndex != index) {swap(&heap->arr[index], &heap->arr[maxIndex]);heapifyDown(heap, maxIndex); // 遞歸向下調整}
}/*** @brief 插入一個元素到最大堆* 將新元素放到數組末尾，然后向上調整以維護堆性質。** @param heap 指向MaxHeap的指針* @param value 要插入的值* @return true 插入成功* @return false 堆已滿，插入失敗*/
bool insert(MaxHeap* heap, int value) {if (isFull(heap)) {printf("Error: Heap is full. Cannot insert %d.\n", value);return false;}heap->arr[heap->size] = value; // 將新元素放到數組末尾heap->size++;                 // 堆大小加1heapifyUp(heap, heap->size - 1); // 從新元素位置向上調整printf("Inserted: %d\n", value);return true;
}/*** @brief 從最大堆中刪除最大元素（根元素）* 將根元素與最后一個元素交換，然后刪除最后一個元素，最后向下調整新的根元素。** @param heap 指向MaxHeap的指針* @param deletedValue 用于存儲被刪除的值的指針* @return true 刪除成功* @return false 堆為空，刪除失敗*/
bool deleteMax(MaxHeap* heap, int* deletedValue) {if (isEmpty(heap)) {printf("Error: Heap is empty. Cannot delete.\n");return false;}*deletedValue = heap->arr[0]; // 存儲根元素的值heap->arr[0] = heap->arr[heap->size - 1]; // 將最后一個元素移動到根heap->size--;                            // 堆大小減1heapifyDown(heap, 0);                    // 從根節點向下調整printf("Deleted Max: %d\n", *deletedValue);return true;
}/*** @brief 查看最大堆的根元素（最大值）** @param heap 指向MaxHeap的指針* @param peekedValue 用于存儲查看到的值的指針* @return true 查看成功* @return false 堆為空，查看失敗*/
bool peekMax(MaxHeap* heap, int* peekedValue) {if (isEmpty(heap)) {printf("Error: Heap is empty. No max element.\n");return false;}*peekedValue = heap->arr[0];printf("Peeked Max: %d\n", *peekedValue);return true;
}/*** @brief 打印堆的當前元素（按數組順序）* 注意：這只是打印數組內容，不代表堆的樹形結構。*/
void printHeap(MaxHeap* heap) {printf("Heap elements (array order): [");for (int i = 0; i < heap->size; i++) {printf("%d", heap->arr[i]);if (i < heap->size - 1) {printf(", ");}}printf("] (Size: %d, Capacity: %d)\n", heap->size, heap->capacity);
}/*** @brief 將一個無序數組構建成一個最大堆* 從最后一個非葉子節點開始，依次向上調整每個節點。* 時間復雜度：O(n)** @param heap 指向MaxHeap的指針* @param arr 待構建的原始數組* @param size 原始數組的大小* @return true 成功構建* @return false 原始數組大小超過堆容量*/
bool buildHeap(MaxHeap* heap, int* arr, int size) {if (size > heap->capacity) {printf("Error: Array size (%d) exceeds heap capacity (%d).\n", size, heap->capacity);return false;}for (int i = 0; i < size; i++) {heap->arr[i] = arr[i];}heap->size = size;// 從最后一個非葉子節點開始向上調整// 最后一個非葉子節點的索引是 (size / 2) - 1for (int i = (heap->size / 2) - 1; i >= 0; i--) {heapifyDown(heap, i);}printf("Heap built from array. \n");return true;
}// -----------------------------------------------------------
// 4. 主函數進行測試
// -----------------------------------------------------------
int main() {MaxHeap* myHeap = createMaxHeap(10); // 創建一個容量為10的堆// 插入操作測試insert(myHeap, 30);insert(myHeap, 10);insert(myHeap, 50);insert(myHeap, 20);insert(myHeap, 40);printHeap(myHeap); // 期望: [50, 40, 30, 10, 20] (或其他有效堆排列)// 查看最大值測試int maxVal;peekMax(myHeap, &maxVal); // 期望: 50// 刪除操作測試deleteMax(myHeap, &maxVal); // 期望: 刪除 50printHeap(myHeap); // 期望: [40, 20, 30, 10] (或其他有效堆排列)deleteMax(myHeap, &maxVal); // 期望: 刪除 40printHeap(myHeap); // 期望: [30, 20, 10] (或其他有效堆排列)// 插入更多元素直到滿insert(myHeap, 60);insert(myHeap, 70);insert(myHeap, 5);insert(myHeap, 90);insert(myHeap, 80);insert(myHeap, 100);insert(myHeap, 15);printHeap(myHeap); // 期望: 堆滿，10個元素// 嘗試插入超出容量insert(myHeap, 101); // 期望: 插入失敗提示// 從數組建堆測試MaxHeap* anotherHeap = createMaxHeap(8);int arr[] = {3, 9, 2, 8, 1, 6, 7, 5};int n = sizeof(arr) / sizeof(arr[0]);printf("\nBuilding heap from array: ");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");buildHeap(anotherHeap, arr, n);printHeap(anotherHeap); // 期望: [9, 8, 7, 5, 1, 6, 2, 3] (或其他有效堆排列)deleteMax(anotherHeap, &maxVal);printHeap(anotherHeap);// 釋放內存destroyMaxHeap(myHeap);destroyMaxHeap(anotherHeap);return 0;
}

代碼解釋：

1. MaxHeap?結構體：

   • arr: 指向存儲堆元素的動態數組。

   • capacity: 數組的最大容量。

   • size: 堆中當前元素的數量，也是下一個要插入元素的索引。

2. 輔助函數：

   • swap(): 簡單的值交換函數。

   • getParentIndex(),?getLeftChildIndex(),?ietRightChildIndex(): 根據數組索引計算父子節點索引。

   • hasLeftChild(),?hasRightChild(): 判斷一個節點是否有對應的子節點，防止越界。

   • isEmpty(),?isFull(): 檢查堆的狀態。

3. 核心堆操作：

   • createMaxHeap()?/?destroyMaxHeap():?堆的內存分配與釋放。

   • heapifyUp(index)?(向上調整):

     • 當新元素插入到堆的末尾時，它可能比其父節點大，違反了最大堆性質。

     • heapifyUp?將該元素與其父節點比較，如果大于父節點則交換位置。

     • 這個過程持續向上，直到元素回到正確位置（不大于父節點）或到達根節點。

     • 時間復雜度：?O(log N)，N 是堆的大小（因為每次操作向上移動一層）。

   • heapifyDown(index)?(向下調整):

     • 當刪除根節點（最大元素）后，或在建堆過程中，根節點被替換為最后一個元素，可能比其子節點小。

     • heapifyDown?將當前節點與其左右子節點比較，找出最大的子節點。

     • 如果當前節點小于最大的子節點，則與最大的子節點交換位置，然后對交換后的子節點位置遞歸調用?heapifyDown。

     • 這個過程持續向下，直到元素回到正確位置（不小于任何子節點）或到達葉子節點。

     • 時間復雜度：?O(log N)。

   • insert(value):

     • 將新元素添加到數組的末尾（heap->arr[heap->size]）。

     • heap->size?增加。

     • 調用?heapifyUp?從新元素的位置向上調整，恢復堆性質。

     • 時間復雜度：?O(log N)。

   • deleteMax(deletedValue):

     • 如果堆為空，返回失敗。

     • 保存根節點的值（heap->arr[0]）作為返回值。

     • 將數組的最后一個元素移動到根節點位置（heap->arr[0] = heap->arr[heap->size - 1]）。

     • heap->size?減少。

     • 調用?heapifyDown?從根節點位置向下調整，恢復堆性質。

     • 時間復雜度：?O(log N)。

   • peekMax():?返回根元素的值，不刪除。

   • buildHeap(arr, size)?(建堆):

     • 將給定數組的元素直接復制到堆的內部數組中。

     • 從最后一個非葉子節點開始（索引為?(size / 2) - 1），向上遍歷到根節點。

     • 對每個非葉子節點調用?heapifyDown，確保其子樹滿足堆性質。

     • 時間復雜度：?O(N)。這比 N 次?insert?操作（O(N log N)）更高效。