acwing 堆排序

ACWing是一家知名的在线编程学习平台，它提供多种计算机科学和技术课程，包括数据结构与算法的讲解。堆排序是一种基于比较的、非稳定的排序算法，其基本思想是利用堆这种特殊的树形数据结构来进行排序。堆可以分为最大堆和最小堆，堆排序主要分为两个步骤：

1. **建堆**：将待排序数组构建成一个大顶堆（最大堆），保证父节点的值大于或等于子节点的值。这一步通常从最后一个非叶子节点开始，自下而上调整堆的性质。

2. **排序**：首先取出堆顶元素（即当前的最大值或最小值），然后将堆的最后一个元素放到堆顶，再对剩余的n-1个元素重新调整成堆。这个过程反复进行，直到堆的大小为1，此时整个序列就被排好序了。

堆排序的时间复杂度为O(nlogn)，空间复杂度为O(1)，因为它是在原地进行排序，不需要额外的存储空间。堆排序适合于数据量较大，对稳定性要求不高的场景。

相关问题

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是序列的长度。

AcWing 838. 堆排序

堆排序是一种高效的排序算法，它利用了堆的数据结构来实现排序。堆是一个完全二叉树，具有以下性质：对于任意节点 i，其父节点的值小于等于子节点的值。

堆排序的基本思路如下：

1. 构建最大堆：将待排序的数组看作是一个完全二叉树，从最后一个非叶子节点开始，依次向上调整每个节点，使得以该节点为根的子树满足最大堆的性质。
2. 将堆顶元素与最后一个元素交换：将最大堆的堆顶元素（即数组的第一个元素）与数组最后一个元素交换位置，此时最大元素就位于数组的最后。
3. 调整堆：将剩余元素重新调整为最大堆。
4. 重复步骤 2 和步骤 3，直到所有元素都排序完成。

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

#include <iostream>
using namespace std;

// 调整以 root 为根的子树为最大堆
void heapify(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], 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[] = {4, 10, 3, 5, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    heapSort(arr, n);

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

以上就是堆排序的基本思路和实现方法。堆排序的时间复杂度为 O(nlogn)，其中 n 为数组的长度。