使用C++实现堆排序算法

堆排序算法的C++实现¶

堆排序是一种基于堆数据结构的高效排序算法，它利用堆的特性（完全二叉树的结构），通过反复调整堆来实现排序。堆排序的时间复杂度为O(n log n)，空间复杂度为O(1)，适合处理大规模数据。

一、堆的基本概念¶

堆是一种特殊的完全二叉树，分为大顶堆和小顶堆：
- 大顶堆：每个父节点的值大于或等于其子节点的值（父 >= 子）。
- 小顶堆：每个父节点的值小于或等于其子节点的值（父 <= 子）。

堆排序通常使用大顶堆，因为每次可以取出堆顶的最大值。

二、堆的存储结构¶

堆可以用数组表示，数组的索引与节点位置的关系如下：
- 对于数组中索引为 i 的节点：
- 父节点索引：(i - 1) / 2（向下取整）
- 左子节点索引：2 * i + 1
- 右子节点索引：2 * i + 2

例如，数组 [12, 11, 13, 5, 6, 7] 对应的堆结构为：

三、堆排序的核心步骤¶

堆排序分为两步：构建初始大顶堆和排序过程。

构建初始大顶堆：将无序数组调整为大顶堆。从最后一个非叶子节点开始，逐个向上调整，确保每个子树满足大顶堆性质。
排序过程：
- 交换堆顶（最大值）与未排序部分的最后一个元素。
- 缩短未排序部分的长度，调整堆（向下调整）。
- 重复上述步骤，直到所有元素排序完成。

四、C++代码实现¶

#include <iostream>
#include <vector>
using namespace std;

// 交换两个元素的值
void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

// 调整以i为根的子树为大顶堆（迭代实现）
void max_heapify(vector<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) {
            swap(arr[i], arr[largest]);
            i = largest; // 调整被交换的子节点
        } else {
            break; // 已满足大顶堆性质，停止调整
        }
    }
}

// 堆排序主函数
void heap_sort(vector<int>& arr) {
    int n = arr.size();

    // 步骤1：构建初始大顶堆
    // 从最后一个非叶子节点开始向上调整
    for (int i = n / 2 - 1; i >= 0; --i) {
        max_heapify(arr, n, i);
    }

    // 步骤2：排序过程
    for (int i = n - 1; i > 0; --i) {
        // 交换堆顶（最大值）与未排序部分的末尾元素
        swap(arr[0], arr[i]);
        // 调整剩余部分的堆（长度为i）
        max_heapify(arr, i, 0);
    }
}

int main() {
    // 测试用例
    vector<int> arr = {12, 11, 13, 5, 6, 7};
    cout << "排序前的数组：";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    // 调用堆排序
    heap_sort(arr);

    // 输出排序结果
    cout << "排序后的数组：";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

五、代码解析¶

swap函数：简单交换两个整数的值。
max_heapify函数：确保以 i 为根的子树满足大顶堆性质。通过迭代比较当前节点与子节点，若子节点更大则交换，直到子树满足大顶堆条件。
heap_sort函数：
- 构建堆：从最后一个非叶子节点（n/2 - 1）开始，逐个向上调用 max_heapify，形成初始大顶堆。
- 排序：将堆顶（最大值）与未排序部分的末尾元素交换，缩短未排序部分长度，再次调用 max_heapify 调整堆，重复直到所有元素排序完成。

六、运行结果¶

排序前的数组：12 11 13 5 6 7 
排序后的数组：5 6 7 11 12 13

堆排序通过高效利用堆的特性，实现了稳定的O(n log n)时间复杂度，是一种经典的排序算法。初学者可通过逐步理解堆的构建和调整过程，掌握其核心思想。