c++ 堆排序，实现数组的升序排列

堆排序是一种基于比较的排序算法，它利用了二叉堆数据结构的特点。在C++中，堆排序通常分为两个步骤：建堆和调整堆。

**建堆**：
首先，将待排序的数组构建成一个最大堆，即数组的第一个元素是最小值，满足每个节点都大于其左右子节点的条件。这通常通过自底向上的方式对数组逐级调整，直到整个数组形成堆。

**调整堆**：
然后，将堆顶（最大值）与最后一个元素交换，这样就得到了有序序列的第一个元素。接着，删除最后一个元素（最大值），并将剩余的n-1个元素重新调整成堆。这个过程会一直重复，每次都将当前堆顶的最大值放到正确的位置，直到整个数组有序。

以下是简单的C++堆排序示例：

#include <iostream>
using namespace std;

// 堆化操作
void heapify(int arr[], int n, int i) {
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;

    // 如果左孩子比根节点大
    if (l < n && arr[l] > arr[largest])
        largest = l;

    // 如果右孩子比根节点或左孩子大
    if (r < n && arr[r] > arr[largest])
        largest = r;

    // 如果根节点不是最大的，则交换它们并递归地堆化新的根节点
    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[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";
    for (int i=0; i<n; ++i)
        cout << arr[i] << " ";

    heapSort(arr, n);

    cout << "\nSorted array: ";
    for (int i=0; i<n; ++i)
        cout << arr[i] << " ";

    return 0;
}