AcWing 839. 堆排序

堆排序是一种基于堆数据结构的排序算法。它通过将待排序的序列构建成一个大顶堆（或小顶堆），然后依次将堆顶元素与最后一个元素交换，并重新调整堆，直到整个序列有序。

具体的堆排序算法如下：

1. 构建初始堆：将待排序序列构建成一个大顶堆。从最后一个非叶子节点开始，依次向前调整每个节点，使其满足大顶堆的性质。这一过程称为“下沉”操作。

2. 将堆顶元素与最后一个元素交换：将堆顶元素与待排序序列的最后一个元素进行交换，此时最后一个元素即为当前序列的最大值。

3. 重新调整堆：将交换后的堆顶元素进行“下沉”操作，使其满足大顶堆的性质。

4. 重复步骤2和3，直到整个序列有序。

下面是C++实现堆排序的代码：

#include <iostream>
#include <vector>

using namespace std;

// 下沉操作
void heapify(vector<int>& nums, int n, int i) {
    int largest = i; // 初始化最大值为当前节点
    int left = 2 * i + 1; // 左子节点
    int right = 2 * i + 2; // 右子节点

    // 如果左子节点大于根节点，则更新最大值
    if (left < n && nums[left] > nums[largest]) {
        largest = left;
    }

    // 如果右子节点大于最大值，则更新最大值
    if (right < n && nums[right] > nums[largest]) {
        largest = right;
    }

    // 如果最大值不是当前节点，则交换节点，并继续调整堆
    if (largest != i) {
        swap(nums[i], nums[largest]);
        heapify(nums, n, largest);
    }
}

// 堆排序
void heapSort(vector<int>& nums) {
    int n = nums.size();

    // 构建初始堆，从最后一个非叶子节点开始向前调整
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(nums, n, i);
    }

    // 依次将堆顶元素与最后一个元素交换，并重新调整堆
    for (int i = n - 1; i > 0; i--) {
        swap(nums[0], nums[i]);
        heapify(nums, i, 0);
    }
}

int main() {
    vector<int> nums = {4, 2, 6, 8, 5, 7};
    heapSort(nums);

    cout << "Sorted array: ";
    for (int num : nums) {
        cout << num << " ";
    }
    
    return 0;
}

以上是堆排序的C++实现代码，通过构建初始堆和重复交换堆顶元素的过程，最终实现了对序列的排序。时间复杂度为O(nlogn)，其中n是序列的长度。