AcWing 838. 堆排序(非递归实现)
原题链接
简单
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
int h[N],idx;
int n,m;
void down(int pos){
int d = pos;
int s = pos*2;
while(s <= n){
if(s+1 <= n && h[s] > h[s+1]) s++;
if(h[d] < h[s]) return;
swap(h[d],h[s]);
d = s;
s = d*2;
}
}
void heap_init(){
for(int i = n/2; i > 0; i--){
down(i);
}
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++){
scanf("%d",&h[i]);
}
heap_init();
for(int i = 0; i < m; i++){
printf("%d ",h[1]);
h[1] = h[n];
n--;
down(1);
}
}