堆排序算法（C++版）

1、介绍

堆排序（Heap Sort）是一种基于二叉堆数据结构的排序算法。它的基本思想是先将待排序的元素构建成一个二叉堆，然后依次将堆顶元素与堆中最后一个元素交换，调整堆，重复此过程直到整个数组有序。

2、堆排序步骤

以下是堆排序的主要步骤：

构建堆（Build Heap）： 将待排序的数组看作是一个完全二叉树，并从最后一个非叶子节点开始，依次向前调整每个节点，使得每个节点都满足堆的性质（父节点的值大于等于/小于等于其子节点的值，具体取决于是构建最大堆还是最小堆）。

排序（Heapify）： 将堆顶元素与堆中最后一个元素交换，然后将堆的大小减一，调整堆使得剩余的元素仍然满足堆的性质。重复这个过程直到堆为空。

3、完整代码

#include <iostream>
#include <vector>

using namespace std;

// 交换数组中两个元素的位置
void swap(vector<int>& arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

// 调整堆，确保以root为根的子树满足堆的性质
void heapify(vector<int>& arr, int n, int root) {
    int largest = root; // 初始化根节点为最大值
    int left = 2 * root + 1; // 左子节点索引
    int right = 2 * root + 2; // 右子节点索引

    // 比较左子节点与根节点
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    // 比较右子节点与当前最大值
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    // 如果最大值不是根节点，则交换它们，并递归调整被影响的子树
    if (largest != root) {
        swap(arr, root, largest);
        heapify(arr, n, largest);
    }
}

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

    // 构建最大堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // 交换堆顶元素与最后一个元素，然后调整堆
    for (int i = n - 1; i >= 0; i--) {
        swap(arr, 0, i);
        heapify(arr, i, 0);
    }
}

int main() {
    vector<int> arr = {12, 11, 13, 5, 6, 7};

    cout << "Original array: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    // 调用堆排序函数
    heapSort(arr);

    cout << "Sorted array: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}