AcWing 838. 堆排序
原题链接
简单
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
int h[N], cnt;
int n, m;
void down(int u) //元素下沉
{
int t = u; // 定义一个替换元素t,每次递归将上一次的u更新为t
if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
// 当该元素的左孩子存在且左孩子小于该结点的时候,
if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
// 当该元素的右孩子存在且右孩子小于该结点的时候,
if (u != t) // 只要u不等于t(只要存在左孩子或右孩子小于根结点
{
swap(h[u], h[t]); // 交换根结点和左(右)结点
down(t); // 递归下沉
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
cnt = n; // 记录当前有多少个结点
for (int i = n / 2; i; i -- ) down(i);
// 直接选取中间的元素进行堆排序
while (m -- )
{
printf("%d ", h[1]);
h[1] = h[cnt -- ];
down(1);
}
puts("");
return 0;
}