堆排序（详解）c++

堆排序（可以⽤ ppt 演⽰流程）堆排序(Heap Sort)是指利⽤堆这种数据结构所设计的⼀种排序算法。本质上是优化了选择排序算法，选择排序的思想是在堆排序元素中拿出最大值或最小值，然后把这个位置的值放在它该放的位置上就可以了，重复这个操作直到整个数组有序，堆排序是将数据全部放到堆这个数据结构，就能快速地找出最大值以及最小值

大家可能会想到以前学过的模拟堆的操作，给一个数组把里面全部的数放到堆里，重复拿出堆顶再删除堆顶的操作，整个数组就变得有序了，这个算法虽然能够将整个数组排成有序的，但需要额外创建一个堆，实际上堆排序是不需要创建一个堆的，因为本身有一个数组了，堆排序是先把数组调整成堆，然后再让整个数组有序，因此堆排序是不需要创建额外的堆，直接在原始数组上操作即可

堆排序的过程分两步：

建堆。升序建⼤堆，降序建⼩堆。建堆过程，从倒数第⼀个⾮叶⼦节点开始，倒着⼀直到根结点位置，每个结点进⾏向下调整。
排序。删除堆顶的逻辑。每次将堆顶元素与堆中最后⼀个元素交换，然后将堆顶元素往下调整。直到堆中剩余⼀个元素，所有元素就都有序了。因此，堆排序仅需⽤到向下调整算法

第一步：建堆

建堆是将待排序数组的基础上，使其变成一个堆。
流程:从倒数第一个非叶子结点开始，执行向下调整算法，直到根结点。它的核心思想，就是从倒数第一个非叶子节点开始，从小堆调整到大堆，根节点开始向下调整完之后，整个数组就变成堆了

第二步：排序

在大根堆的基础上，用选择排序的思想将数组调整成有序状态。
流程:每次将堆顶元素与堆中最后一个元素交换，堆的大小减一，然后将堆顶元素向下调整。重复这个过程，直到堆中剩下一个元素。

代码：

测试链接：P1177 【模板】排序 - 洛谷

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int n;
int a[N];

void down(int p, int len)
{
    int c = p * 2;
    while (c <= len)
    {
        if (c + 1 <= len && a[c + 1] > a[c]) ++c;
        if (a[p] >= a[c]) return;

        swap(a[p], a[c]);
        p = c;
        c = p * 2;
    }
}

void heap_sort()
{
    //1.建堆
    //最后一个节点(n)的父亲肯定是根叶节点(n/2)
    for (int i = n / 2; i >= 1; --i)
    {
        //每个节点执行向下调整算法
        down(i, n);
    }

    //2.排序
    //每次拿堆顶和最后一个元素交换
    for (int i = n; i > 1; --i) // 枚举堆里面最后一个元素的位置
    {
        swap(a[i], a[1]);
        //swap完后，大的数放到后面的有序序列，减少一个要排序的数
        //第一个参数，从哪个点开始向下调整，第二个参数，当前堆大小是多少
        down(1, i - 1); 
    }
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    heap_sort();

    for (int i = 1; i <= n; i++) cout << a[i] << " ";

    return 0;
}