堆排序

题目描述
堆排序是一种基于比较的排序算法，它利用堆这种数据结构（通常是二叉堆）来进行排序。堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。

输入格式
输入共 2 行，第一行是一个整数 n，表示数组的长度。第二行包含 n 个整数，表示待排序的数组。

输出格式
输出共 1 行，包含 n 个整数，表示排序后的数组（升序排列）。

数据范围
1 ≤ n ≤ 10000
-10000 ≤ 数组元素 ≤ 10000

输入样例：

10
4 10 3 5 1 8 7 2 9 6

输出样例：

1 2 3 4 5 6 7 8 9 10

注意事项

• 堆排序的时间复杂度为 O(nlogn)，空间复杂度为 O(1)。
• 堆排序是不稳定的排序算法。
• 堆排序特别适合于需要找出最大或最小元素的场景。

代码实现

#include <iostream>
using namespace std;

// 交换两个元素
void swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}

// 调整堆，使其满足最大堆的性质
void heapify(int a[], int n, int i)
{
    int largest = i; // 初始化largest为根节点
    int left = 2 * i + 1; // 左子节点
    int right = 2 * i + 2; // 右子节点
    
    // 如果左子节点大于根节点
    if (left < n && a[left] > a[largest])
    {
        largest = left;
    }
    
    // 如果右子节点大于目前的最大值
    if (right < n && a[right] > a[largest])
    {
        largest = right;
    }
    
    // 如果最大值不是根节点，则交换并继续调整堆
    if (largest != i)
    {
        swap(a[i], a[largest]);
        heapify(a, n, largest); // 递归地调整受影响的子树
    }
}

// 堆排序函数
void heapSort(int a[], int n)
{
    // 构建最大堆（从最后一个非叶子节点开始向上调整）
    for (int i = n / 2 - 1; i >= 0; i--)
    {
        heapify(a, n, i);
    }
    
    // 一个个从堆顶取出元素
    for (int i = n - 1; i > 0; i--)
    {
        // 将当前堆顶（最大值）移到数组末尾
        swap(a[0], a[i]);
        
        // 对剩余的堆进行调整，使其重新满足最大堆的性质
        heapify(a, i, 0);
    }
}

int main()
{
    int n;
    cin >> n;
    int a[n];
    
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    
    heapSort(a, n); // 对整个数组进行堆排序
    
    // 输出排序后的数组
    for (int i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
    
    return 0;
}

时间复杂度

• 时间复杂度：O(nlogn)，其中 n 为数组的长度。
• 空间复杂度：O(1)。

代码解释

• 堆排序的核心思想是首先将数组构建成一个最大堆，然后依次将堆顶元素（最大值）与堆的最后一个元素交换，并重新调整堆，使其满足最大堆的性质。
• 构建最大堆的时间复杂度为 O(n)，而调整堆的时间复杂度为 O(logn)，需要调整 n-1 次，因此总的时间复杂度为 O(n + (n-1)logn) = O(nlogn)。
• 在这个实现中，我们使用数组来表示二叉堆，对于索引为 i 的节点，其左子节点的索引为 2i+1，右子节点的索引为 2i+2，父节点的索引为 (i-1)/2（整数除法）。