堆排序（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. 优化方向：

   • 小规模数据用插入排序优化

   • 循环展开加速堆调整

   • 多线程并行处理子树调整

堆排序是高效排序算法的基石，也是优先级队列的核心实现。理解其原理对掌握高级数据结构至关重要。