堆排序（小根堆）

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;

int h[N], cnt;
int n, m;
void down(int u)
{
    int t = u;//t 是这三个点中的最小值
    if(u * 2 <= cnt && h[u * 2] < h[t]) t = 2 * u;
    if(u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = 2 * u + 1;
    if(u != t)//当前根节点！=最小数 说明要更新
    {
        swap(h[u], h[t]);//交换
        down(t);//交换完之后递归t位置
    }
}
int main()
{

    cin >> n >> m;
    cnt = n;

    for(int i = 1; i <= n; i ++) cin >> h[i];

    for(int i = n / 2; i; i --) down(i);//最后一层不需要再down所以n/2

    while(m --)
    {
        cout << h[1] << " ";//头元素最小（根节点）
        h[1] = h[cnt];//让最后一个点覆盖根节点
        cnt --;//减少元素
        down(1);//递归当前根节点
    }
    return 0;
}

大根堆

#include <iostream>

using namespace std;

const int N = 100010;

int h[N], sz;
int n;

void down(int u)
{
    int t = u;
    if(2 * u <= sz && h[2 * u] > h[t]) t = 2 * u;
    if(2 * u + 1 <= sz && h[2 * u + 1] > h[t]) t = 2 * u + 1;
    if(u != t)
    {
        swap(h[u], h[t]);
        down(t);
    }
}
void heap_sort()
{
    sz = n;
    for(int i = n / 2; i; i --) down(i);
    for(int i = 1; i <= n - 1; i ++)
     {
        swap(h[1], h[sz]);
        sz --;
        down(1);
        for(int i = 1;i <= n; i ++) cout << h[i] << " ";
        cout << endl;
    }
}
int main()
{
    cin >> n;

    for(int i = 1;i <= n; i ++) cin >> h[i];

    heap_sort();

    for(int i = 1;i <= n; i ++) cout << h[i] << " ";
    return 0;
}

模拟数据：
5
3 1 2 4 5

输出
4 3 2 1 5
3 1 2 4 5
2 1 3 4 5
1 2 3 4 5
1 2 3 4 5

新代码

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

const int N = 100010;

int n, h[N], sz;

void down(int u)
{

    int t = u;

    if(u * 2 <= sz && h[u * 2] < h[t]) t = u * 2;
    if(u * 2 + 1 <= sz && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if(u != t)
    {
        swap(h[u], h[t]);
        down(t);
    }
}
// void down(int u)
// {
//     int t = u;
//     if (u * 2 <= sz && q[u * 2] > q[t]) t = u * 2;
//     if (u * 2 + 1 <= sz && q[u * 2 + 1] > q[t]) t = u * 2 + 1;

//     if (u != t)
//     {
//         swap(q[u], q[t]);
//         down(t);
//     }
// }
void heap_sort()
{
    sz = n;
    for(int i = n / 2; i; i --) down(i);
    for(int i = 1; i <= n; i ++) 
    {
        cout << h[1] << " ";
        h[1] = h[sz];
        sz --;
        down(1);
    }
}
// void heap_sort()  // 堆排序，下标一定要从1开始
// {
//     sz = n;
//     for (int i = n / 2; i; i -- ) down(i);

//     for (int i = 0; i < n - 1; i ++ )
//     {
//         swap(q[1], q[sz]);
//         sz -- ;
//         down(1);
//     }
// }
int main()
{
    cin >> n;

    for(int i = 1; i <= n; i ++) cin >> h[i];

    heap_sort();
    // for(int i = 1; i <= n; i ++) cout <<  h[i] << " ";

    return 0;
}