堆排序步骤及c++代码

堆排序是一种使用堆数据结构进行排序的算法。堆是一种特殊的二叉树结构，具有以下性质：对于每个节点i，其父节点为(i-1)/2，左子节点为2*i+1，右子节点为2*i+2。堆排序的基本思想是将待排序的数组构建成一个最大堆（或最小堆），然后不断地将堆顶元素与堆的最后一个元素交换，并进行堆调整操作，直到所有元素都被排序。以下是堆排序的步骤：

1. 构建最大堆（或最小堆）：从待排序数组中构建一个二叉堆，使得每个父节点的值都大于（或小于）它的子节点的值。
2. 交换堆顶元素与堆的最后一个元素：将堆顶元素与堆的最后一个元素交换位置，将最大值（或最小值）放在数组的末尾。
3. 进行堆调整：对交换后的堆进行调整，使其满足堆的性质。
4. 重复步骤2和步骤3，直到所有元素都被排序。

以下是使用C++实现堆排序的代码示例：

#include <iostream>
using namespace std;

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);
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    heapSort(arr, n);

    cout << "排序后的数组：\n";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

这段代码中，定义了一个`heapify`函数用于进行堆调整操作，使得以节点i为根的子树满足堆的性质。然后，通过`heapSort`函数进行堆排序，首先构建最大堆，然后不断地交换堆顶元素与堆的最后一个元素，并进行堆调整。在`main`函数中，声明了一个待排序的数组`arr`，然后通过调用`heapSort`函数对其进行排序。最后，打印出排序后的数组。

运行以上代码，输出结果为：11 12 22 25 64，表示数组已成功排序。