?叉樹性質（左右孩子位置）

實現堆的順序結構

堆的結構體

typedef int HPDataType;  // 堆中存儲的數據類型
typedef struct Heap {HPDataType* arr;    // 存儲堆元素的數組int size;           // 當前堆中元素的數量int capacity;       // 堆的容量
} HP;

核心函數功能

• HPInit：初始化堆，將數組指針置空，大小和容量設為 0
• HPDestroy：銷毀堆，釋放動態分配的內存
• HPPrint：打印堆中的所有元素
• Swap：交換兩個整數的值
• AdjustUp：向上調整算法，用于插入元素后維持堆的性質
• HPPush：向堆中插入元素
• HPEmpty：判斷堆是否為空
• AdjustDown：向下調整算法，用于刪除元素后維持堆的性質
• HPPop：刪除堆頂元素
• HPTop：獲取堆頂元素的值

void HPInit(HP* php);
void HPDestroy(HP* php);
void HPPrint(HP* php);void Swap(int* x, int* y);
void AdjustUp(HPDataType* arr, int child);
void AdjustDown(HPDataType* arr, int parent, int n);void HPPush(HP* php, HPDataType x);
void HPPop(HP* php);
//取堆頂數據
HPDataType HPTop(HP* php);// 判空
bool HPEmpty(HP* php);

初始化

void HPInit(HP* php)
{php->arr = NULL;php->size = php->capacity = 0;
}

打印

void HPPrint(HP* php)
{for (int i = 0; i < php->size; i++){printf("%d ", php->arr[i]);}printf("\n");
}

交換數據

void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}

如果不用指針，直接傳遞變量的值，函數內部的交換操作不會影響到函數外部的變量

向上調整法

void AdjustUp(HPDataType* arr, int child)
{int parent = (child - 1) / 2;while (child > 0){//大堆：>//小堆：<if (arr[child] > arr[parent]){//調整Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else {break;}}
}

當新元素被插入到堆的末尾時，可能會破壞堆的性質（父節點值大于子節點值）。AdjustUp?函數通過將新插入的元素（從最后一個位置）向上移動，與父節點比較并交換，直到重新滿足堆的性質。

細節：

1. 父節點索引計算公式?(child - 1) / 2?是由完全二叉樹的性質決定的

2. 循環終止條件?child > 0?確保不會越界訪問（根節點沒有父節點）

3. 若要實現小根堆，只需將比較運算符?>?改為?<

入堆

//入堆
void HPPush(HP* php, HPDataType x)
{assert(php);//判斷空間是否足夠if (php->size == php->capacity){int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapacity * sizeof(HPDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}php->arr = tmp;php->capacity = newCapacity;}php->arr[php->size] = x;//向上調整AdjustUp(php->arr, php->size);++php->size;
}

• 新元素先放在數組末尾（對應完全二叉樹的最后一個位置）
• 調用AdjustUp函數向上調整，確保插入后仍滿足堆的性質
• 最后更新堆的元素數量

注意：

realloc?的核心作用是重新分配已有的動態內存塊，可以：

• 當原內存塊后面有足夠空間時，直接在原地擴展，無需復制數據
• 當空間不足時，自動分配新內存塊并將原數據復制過去
  而?malloc?只能分配全新的內存塊，如果用?malloc?實現擴容，需要手動完成
• 當堆的內存塊后面有連續的空閑空間時，realloc?可以直接擴展內存，避免數據復制，效率遠高于?malloc?+?memcpy?+?free?的組合。

時間復雜度

• 擴容操作的時間復雜度：O (n)（最壞情況，需要復制所有元素），但由于采用 2 倍擴容策略，平均下來是 O (1)
• 向上調整操作的時間復雜度：O (log n)（最多需要調整到根節點，路徑長度為堆的高度）
• 因此，HPPush操作的平均時間復雜度為 O (log n)。

判空

// 判空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}

向下調整法

//向下調整算法
void AdjustDown(HPDataType* arr, int parent, int n)
{int child = parent * 2 + 1;//左孩子while (child < n){//大堆：<//小堆：>if (child + 1 < n && arr[child] < arr[child + 1]){child++;}//大堆: >//小堆：<if (arr[child] > arr[parent]){//調整Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else {break;}}
}

• HPDataType* arr：存儲堆元素的數組
• int parent：需要向下調整的起始父節點索引（通常是堆頂元素索引 0）
• int n：堆中有效元素的個數（調整范圍不超過此值）

• 關鍵細節：

  • 先判斷右孩子是否存在且更大（child + 1 < n確保不越界），目的是找到兩個孩子中的最大值
  • 若子節點大于父節點，交換后繼續向下調整；否則說明已滿足堆性質，停止調整
  • 若要實現小根堆，只需將兩處比較運算符<和>分別改為>和<

帶入實例：

假設大根堆當前狀態為?[60, 50, 40, 30]，刪除堆頂元素后，最后一個元素30移到堆頂，數組變為?[30, 50, 40, ...]（size減 1 后n=3）：

時間復雜度

AdjustDown的時間復雜度為O(log n)，因為最多需要調整到堆的最底層，路徑長度為堆的高度（完全二叉樹的高度為log2(n+1)）。

1. parent=0，child=1（左孩子 50）
2. 右孩子child+1=2（值 40）存在，50>40，所以child保持 1
3. 子節點 50 > 父節點 30，交換后數組為?[50, 30, 40]，parent=1，child=3
4. child=3不小于n=3，循環終止，調整完成，結果為?[50, 30, 40]，滿足大根堆性質

刪除堆頂元素：

void HPPop(HP* php)
{assert(!HPEmpty(php));// 0 php->size-1Swap(&php->arr[0], &php->arr[php->size - 1]);--php->size;//向下調整AdjustDown(php->arr, 0, php->size);
}

• 時間復雜度：O (log n)，主要由AdjustDown操作決定
• 空間復雜度：O (1)，僅使用常數級額外空間

獲取堆頂元素

//取堆頂數據
HPDataType HPTop(HP* php)
{assert(!HPEmpty(php));return php->arr[0];
}

堆的銷毀

void HPDestroy(HP* php)
{if (php->arr)free(php->arr);php->arr = NULL;php->size = php->capacity = 0;
}

測試代碼（堆排序---向下調整法建堆）

void arrPrint(int* arr, int n)
{for (int i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
}
void BubbleSort(int* arr, int n)
{for (int i = 0; i < n; i++){for (int j = 0; j < n - i - 1; j++){if (arr[j] > arr[j + 1]){Swap(&arr[j], &arr[j + 1]);}}}
}//堆排序
void HeapSort1(int* arr, int n)
{HP hp; //——————借助數據結構堆來實現堆排序HPInit(&hp);for (int i = 0; i < n; i++){HPPush(&hp, arr[i]);}int i = 0;while (!HPEmpty(&hp)){int top = HPTop(&hp);arr[i++] = top;HPPop(&hp);}HPDestroy(&hp);
}void HeapSort(int* arr, int n)
{//建堆——向下調整算法建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, i, n);}//堆排序int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdjustDown(arr, 0, end);end--;}}void test01()
{HP hp;HPInit(&hp);HPPush(&hp, 56);HPPush(&hp, 10);HPPush(&hp, 15);HPPush(&hp, 30);//HPPush(&hp, 70);//HPPush(&hp, 25);HPPrint(&hp);HPPop(&hp);HPPrint(&hp);HPPop(&hp);HPPrint(&hp);HPPop(&hp);HPPrint(&hp);HPPop(&hp);HPPrint(&hp);HPDestroy(&hp);
}void test02()
{HP hp;HPInit(&hp);HPPush(&hp, 56);HPPush(&hp, 10);HPPush(&hp, 15);HPPush(&hp, 30);HPPrint(&hp);while (!HPEmpty(&hp)){int top = HPTop(&hp);printf("%d ", top);HPPop(&hp);}HPDestroy(&hp);
}int main()
{//test01();//test02();int arr[6] = { 19,15,20,17,13,10 };printf("排序之前：");arrPrint(arr, 6);//堆排序HeapSort(arr, 6);printf("排序之后：");arrPrint(arr, 6);return 0;
}