C++如何实现堆排序

# C++如何实现堆排序

## 1. 堆排序概述

堆排序（Heap Sort）是一种基于二叉堆数据结构的比较排序算法。它由J. W. J. Williams于1964年提出，具有以下特点：

- **时间复杂度**：O(n log n)（最优、最差和平均情况下）
- **空间复杂度**：O(1)（原地排序）
- **稳定性**：不稳定排序
- **适用性**：适合大数据量排序，尤其是需要部分排序的场景

## 2. 堆的基本概念

### 2.1 二叉堆的定义
二叉堆是完全二叉树，满足以下性质：
- **最大堆**：每个节点的值都大于或等于其子节点的值
- **最小堆**：每个节点的值都小于或等于其子节点的值

### 2.2 堆的存储
通常用数组表示堆，对于索引i的节点：
- 父节点：(i-1)/2
- 左子节点：2*i + 1
- 右子节点：2*i + 2

## 3. 堆排序算法步骤

### 3.1 基本流程
1. 构建最大堆（Build Max Heap）
2. 交换堆顶元素与末尾元素
3. 调整剩余元素使其满足堆性质
4. 重复步骤2-3直到排序完成

### 3.2 关键操作
- **Heapify**：维护堆性质的核心操作
- **Build Heap**：将无序数组构建为堆

## 4. C++实现详解

### 4.1 堆调整函数实现

```cpp
/**
 * 维护堆性质（最大堆）
 * @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) {
        std::swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

4.2 构建堆函数

/**
 * 构建最大堆
 * @param arr 待排序数组
 * @param n 数组大小
 */
void buildHeap(int arr[], int n) {
    // 从最后一个非叶子节点开始调整
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
}

4.3 堆排序主函数

/**
 * 堆排序主函数
 * @param arr 待排序数组
 * @param n 数组大小
 */
void heapSort(int arr[], int n) {
    // 1. 构建初始最大堆
    buildHeap(arr, n);

    // 2. 逐个提取元素
    for (int i = n - 1; i > 0; i--) {
        // 将当前最大值（堆顶）移到数组末尾
        std::swap(arr[0], arr[i]);
        
        // 调整剩余元素
        heapify(arr, i, 0);
    }
}

5. 完整示例代码

#include <iostream>
#include <algorithm>

// 前面定义的heapify、buildHeap和heapSort函数

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    std::cout << "排序前: ";
    for (int i = 0; i < n; i++)
        std::cout << arr[i] << " ";
    std::cout << std::endl;

    heapSort(arr, n);

    std::cout << "排序后: ";
    for (int i = 0; i < n; i++)
        std::cout << arr[i] << " ";
    std::cout << std::endl;

    return 0;
}

6. 算法分析

6.1 时间复杂度分析

• 构建堆：O(n)
• n-1次堆调整：每次O(log n)，总共O(n log n)
• 总复杂度：O(n log n)

6.2 空间复杂度分析

• 仅使用常数个额外空间：O(1)

6.3 稳定性分析

堆排序是不稳定的，因为交换操作可能改变相等元素的相对位置。

7. 优化与变种

7.1 迭代实现Heapify

递归实现可能造成栈溢出，可以改为迭代：

void heapify(int arr[], int n, int i) {
    while (true) {
        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) break;
            
        std::swap(arr[i], arr[largest]);
        i = largest;
    }
}

7.2 最小堆实现

只需修改比较逻辑即可实现升序排序：

void heapify(int arr[], int n, int i) {
    int smallest = i;
    // ... 比较时使用 < 而不是 >
}

8. 实际应用场景

1. 优先级队列实现：堆是优先级队列的理想数据结构
2. Top K问题：只需构建K大小的堆，时间复杂度O(n log k)
3. 游戏开发：频繁需要获取最大/最小值的场景
4. 操作系统：进程调度中的优先级处理

9. 与其他排序算法比较

10. 常见问题解答

Q1：为什么堆排序比快速排序慢？ A：虽然时间复杂度相同，但堆排序的常数因子较大，且访问模式不如快速排序对缓存友好。

Q2：如何选择最大堆还是最小堆？ A：最大堆实现降序排序，最小堆实现升序排序。通常使用最大堆更直观。

Q3：堆排序适合链表结构吗？ A：不适合，因为堆依赖随机访问能力，链表实现效率很低。

11. 总结

堆排序是一种高效的原地排序算法，特别适合以下场景： - 内存受限环境 - 需要同时获取最大值/最小值的应用 - 对最坏情况时间复杂度有要求的场景

通过理解堆数据结构和heapify操作的本质，可以灵活应用堆排序解决各类排序问题。虽然在实际应用中可能不如快速排序快，但其稳定的O(n log n)时间复杂度和O(1)空间复杂度使其在某些特殊场景下不可替代。 “`