算法：堆排序 (Heap Sort)

1. 核心概念

堆排序是利用 堆 (Heap) 这种数据结构所设计的一种排序算法。它是一棵 完全二叉树。

• 大顶堆 (Max Heap)：每个节点的值均 $\ge$ 其左右孩子节点的值。堆顶为最大值。
• 小顶堆 (Min Heap)：每个节点的值均 $\le$ 其左右孩子节点的值。堆顶为最小值。

---

2. 算法流程

1. 初始建堆：将无序序列调整为大顶堆（升序排列常用大顶堆）。
2. 交换与调整：
   • 将堆顶元素（最大值）与末尾元素交换。
   • 将剩余 $n-1$ 个元素重新调整为大顶堆。
3. 循环：重复步骤 2，直到堆中仅剩一个元素。

#include <stdio.h>
 
// 交换两个元素的值
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
 
/**
 * 堆调整函数 (下虑 siftDown)
 * @param arr 待调整数组
 * @param n   数组长度（有效堆大小）
 * @param 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) {
    // 1. 构建大顶堆 (从最后一个非叶子节点开始调整)
    // 最后一个非叶子节点的下标是 n/2 - 1
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
 
    // 2. 一个个从堆顶取出元素
    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 A[] = {2, 8, 7, 1, 3, 5, 6, 4};
    int n = sizeof(A) / sizeof(A[0]);
 
    printf("原始数组: \n");
    printArray(A, n);
 
    heapSort(A, n);
 
    printf("排序后的数组: \n");
    printArray(A, n);
    
    return 0;
}

---

3. 经典题目解析 (软考真题)

题目：对数组 $A=(2,8,7,1,3,5,6,4)$ 构建大顶堆。

构建步骤图解：

1. 完全二叉树初始状态：
   • 根节点为 2，依次排列。
2. 从最后一个非叶子节点开始调整：
   • 节点 1（4的父节点）：$4>1$，交换 $\to (2,8,7,4,3,5,6,1)$
   • 节点 7：孩子 5, 6 都比它小，不调整。
   • 节点 8：孩子 4, 3 都比它小，不调整。
   • 根节点 2：孩子 8, 7 中 8 最大。2 与 8 交换 $\to (8,2,7,4,3,5,6,1)$
3. 下滤调整 (Sift Down)：
   • 2 换位后，发现其孩子 4, 3 中 4 更大。2 继续与 4 交换 $\to (8,4,7,2,3,5,6,1)$

最终答案：C (8, 4, 7, 2, 3, 5, 6, 1)

---

4. 算法分析

特性	复杂度/描述
平均时间复杂度	$O(n\log n)$
空间复杂度	$O(1)$ (原地排序)
稳定性	不稳定
适用场景	适合大数据量，且对空间要求苛刻的情况

---

5. 相关知识点

• 完全二叉树
• 优先队列
• 快速排序 (对比分析)