堆排序 -- 注意headsort中 m的使用
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int h[80000000];
int m;
void siftdown(int i){
int f = 0;
while(i*2<=m){
int t;
if(h[i]<h[i*2])t = i;
else t = i*2;
if((i*2+1)<=m&&h[i*2+1]<h[t])t = i*2+1;
//边界
if(t==i){
//f =1 ;
break;
}
else{
swap(h[i],h[t]);
i = t; //交换
}
}
}
void heapsort(){
int u = m;
while(m>1){
swap(h[1],h[m]);
m--;
siftdown(1);//向下调整
}
}
int main()
{
int n;
cin>>n>>m;
int yy= m;
for(int i=1;i<=m;i++){
scanf("%d",&h[i]);
}
for(int i=m/2;i>=1;i--){
siftdown(i);
}
for(int i=1;i<=n-m;i++){
int num;
scanf("%d",&num);
// cout<<" "<<num<<" "<<endl;
if(num<h[1]);
else{
h[1] = num;
for(int j=m/2;j>=1;j--){
siftdown(j);
}
}
}
int top = 1;
heapsort();
for(int i=1;i<=yy;i++){
if(top)top = 0;
else printf(" ");
printf("%d",h[i]);
}
printf("\n");
return 0;
}
/*
10 8
1 2 4 3 6 5 8 7 10 9
*/
