AcWing 838. 堆排序
原题链接
简单
作者:
一颗种子
,
2025-04-15 11:16:34
· 江苏
,
所有人可见
,
阅读 1
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n,m;
int h[N];
void down(int u){
int t = u;
if(u*2 <= n && h[t] > h[u*2]){
t = u*2;
}
if(u*2+1 <= n && h[t] > h[u*2+1]){
t = u*2+1;
}
if(u!=t){
swap(h[u],h[t]);
down(t);
}
}
int main(){
ios::sync_with_stdio(false);
cin >> n >> m;
for(int i=1;i<=n;i++){
cin >> h[i];
}
for(int i=n/2;i>=1;i--){
down(i);
}
while(m--){
cout << h[1] << " ";
swap(h[1],h[n--]);
down(1);
}
return 0;
}