堆排序（Heap Sort）是一種高效的排序算法，利用二叉堆數據結構實現。其核心思想是將待排序序列構造成一個大頂堆（或小頂堆），通過反復調整堆結構完成排序。下面從原理到實現進行詳細解析。

---

一、核心概念：二叉堆

二叉堆是一種完全二叉樹，滿足以下性質：

• 大頂堆：父節點值 ≥ 子節點值（用于升序排序）

• 小頂堆：父節點值 ≤ 子節點值（用于降序排序）

---

二、堆排序步驟

1. 初始建堆：將無序序列構建成大頂堆

2. 堆排序：反復將堆頂元素與末尾交換，并調整堆

1. 初始建堆（Heapify）

從最后一個非葉子節點開始，自底向上調整堆結構。

關鍵公式（數組下標從0開始）：

• 節點?i?的左子節點：2i + 1

• 節點?i?的右子節點：2i + 2

• 最后一個非葉子節點：n/2 - 1

調整過程：

1. 比較當前節點與左右子節點

2. 若子節點更大，則與最大子節點交換

3. 遞歸調整被影響的子樹

2. 堆排序流程

1. 將堆頂元素（最大值）與末尾元素交換

2. 堆大小減1，重新調整堆頂元素

3. 重復直到堆大小為1

---

三、C語言完整實現

#include <stdio.h>// 交換元素
void swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp;
}// 調整堆（大頂堆）
void heapify(int arr[], int n, int i) {int largest = i;         // 初始化最大值為根節點int left = 2 * i + 1;    // 左子節點下標int right = 2 * i + 2;   // 右子節點下標// 比較左子節點與根節點if (left < n && arr[left] > arr[largest])largest = left;// 比較右子節點與當前最大值if (right < n && arr[right] > arr[largest])largest = right;// 若最大值不是根節點，則交換并遞歸調整if (largest != i) {swap(&arr[i], &arr[largest]);heapify(arr, n, largest);  // 遞歸調整受影響子樹}
}// 堆排序主函數
void heapSort(int arr[], int n) {// 初始建堆：從最后一個非葉子節點開始for (int i = n / 2 - 1; i >= 0; i--)heapify(arr, n, i);// 依次提取堆頂元素for (int i = n - 1; i > 0; i--) {swap(&arr[0], &arr[i]);  // 將堆頂移至末尾heapify(arr, i, 0);      // 調整剩余元素}
}// 測試代碼
int main() {int arr[] = {12, 11, 13, 5, 6, 7};int n = sizeof(arr) / sizeof(arr[0]);printf("原始數組：\n");for (int i = 0; i < n; i++)printf("%d ", arr[i]);heapSort(arr, n);printf("\n排序后數組：\n");for (int i = 0; i < n; i++)printf("%d ", arr[i]);return 0;
}

---

四、算法分析

指標	值	說明
時間復雜度	O(n log n)	建堆O(n)，每次調整O(log n)
空間復雜度	O(1)	原地排序
穩定性	不穩定	交換可能改變相等元素順序
適用場景	大數據量排序	內存受限時優于歸并排序

---

五、關鍵點解析

1. 為什么從n/2-1開始建堆？
   完全二叉樹中，非葉子節點占總數一半，且最后一個非葉子節點的下標為n/2-1。

2. 為何堆排序不穩定？
   交換堆頂與末尾元素時，可能破壞相等元素的原始順序（如[5, 5, 3]）。

3. 優化方向：

   • 小規模數據用插入排序優化

   • 循環展開加速堆調整

   • 多線程并行處理子樹調整

堆排序是高效排序算法的基石，也是優先級隊列的核心實現。理解其原理對掌握高級數據結構至關重要。