在C语言中，堆是一种特殊的树形数据结构，通常用于实现优先队列。堆排序（Heap Sort）是一种利用堆这种数据结构设计的排序算法。

堆的基本概念

1. 定义：堆是一种完全二叉树，分为两种类型：

   • 最大堆（Max Heap）：父节点的键值总是大于或等于子节点的键值。
   • 最小堆（Min Heap）：父节点的键值总是小于或等于子节点的键值。

2. 性质：

   • 完全二叉树：堆必须是完全填满的，除了最后一层，节点都尽可能左对齐。
   • 堆序性：最大堆的堆序性要求父节点大于子节点；最小堆相反。

3. 存储：通常使用数组存储堆，完全二叉树的性质使得这种表示方法非常方便。对于任意位置为i的节点，其父节点位置为(i-1)/2，左子节点位置为2i+1，右子节点为2i+2。

堆排序算法

堆排序由两部分组成：构建堆和排序。

1. 构建最大堆：

   • 从数组的第一个非叶子节点开始下沉调整（从n/2-1到0），调整整个数组成最大堆。

2. 排序过程：

   • 交换堆顶元素（最大元素）与当前堆的最后一个元素。
   • 减少堆的大小，并对新的堆顶进行下沉调整以保持最大堆的性质。
   • 重复以上步骤直到堆大小为1。

C语言实现堆排序

#include <stdio.h>  
// 交换两个整数  
void swap(int *a, int *b) {  
    int temp = *a;  
    *a = *b;  
    *b = temp;  
}  
// 堆化过程，将以i为根的子树调整为堆  
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);  
    }  
}  
// 辅助函数：打印数组  
void printArray(int arr[], int n) {  
    for (int i = 0; i < n; i++)  
        printf("%d ", arr[i]);  
    printf("\n");  
}  
// 主程序  
int main() {  
    int arr[] = {12, 11, 13, 5, 6, 7};  
    int n = sizeof(arr) / sizeof(arr[0]);  
    heapSort(arr, n);  
    printf("Sorted array is \n");  
    printArray(arr, n);  
    return 0;  
}  

总结

堆排序是一种高效的不稳定的排序算法，时间复杂度为O(n log n)，适用于大量数据的排序，虽然其最坏、最好和平均时间复杂度都是一样的。由于其主要用到堆数据结构，也常用于实现优先队列等其他功能。