C++堆排序用vector

可以使用 vector 来实现堆排序，具体步骤如下：

1. 将输入的数组转换为 vector。

2. 构建最大堆，即将 vector 中的元素依次插入堆中。

3. 将堆顶元素（即 vector 的第一个元素）与堆底元素交换位置，并从堆中删除该元素。

4. 对剩余的元素重新进行堆调整，使其满足最大堆的性质。

5. 重复步骤3和步骤4，直到堆中没有元素。

代码如下：

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

// 向下调整堆
void adjustDown(vector<int>& nums, int root, int len) {
    int parent = root;
    int child = 2 * parent + 1;
    while (child < len) {
        if (child + 1 < len && nums[child + 1] > nums[child]) { // 找到较大的孩子节点
            child++;
        }
        if (nums[child] > nums[parent]) { // 如果孩子节点比父节点大，则交换它们的值
            swap(nums[child], nums[parent]);
            parent = child;
            child = 2 * parent + 1;
        } else {
            break;
        }
    }
}

// 堆排序
void heapSort(vector<int>& nums) {
    int len = nums.size();
    // 构建最大堆
    for (int i = len / 2 - 1; i >= 0; i--) {
        adjustDown(nums, i, len);
    }
    // 排序
    for (int i = len - 1; i >= 1; i--) {
        swap(nums[0], nums[i]); // 将堆顶元素与堆底元素交换位置
        adjustDown(nums, 0, i); // 对剩余的元素进行堆调整
    }
}

int main() {
    int arr[] = {5, 3, 8, 6, 4};
    vector<int> nums(arr, arr + 5);

    heapSort(nums);

    for (int i = 0; i < nums.size(); i++) {
        cout << nums[i] << " ";
    }
    cout << endl;

    return 0;
}