acwing838堆排序,堆，简单模板（模板）
堆排序在STL里就是优先队列priority_queue
这里初始化排序
暴力读一个插入尾部然后up上去，时间复杂度NlogN
先全部读入，在n/2开始用down起到优化时间复杂度2N，如下图
1
2 
3 
2 3 重要板块：
void down(int x){//down函数
int p=x;
if((x<<1)<=size&&h[x<<1]<h[p]) p=x<<1;//左儿子是否存在&&左儿子比目前最小的小
if((x<<1|1)<=size&&h[x<<1|1]<h[p]) p=x<<1|1;
if(p!=x) swap(h[p],h[x]),down(p);//如果最小的不是父节点，则更换父节点
} void up(int x){
while(x>>1&&h[x]<h[x>>1]) swap(h[x],h[x>>1]), x>>=1;
} for(int i=1;i<=n;i++) scanf("%d",&h[i]);//输入点
for(int i=n>>1;i;i--) down(i);//桶排序，该更新方式2N时间复杂度 板子： #include <bits/stdc++.h>
using namespace std;
const int N=100005;
int n,m,h[N],size;
void down(int x){
int p=x;
if((x<<1)<=size&&h[x<<1]<h[p]) p=x<<1;//左儿子是否存在&&左儿子比目前最小的小
if((x<<1|1)<=size&&h[x<<1|1]<h[p]) p=x<<1|1;//右儿子同
if(p!=x) swap(h[p],h[x]),down(p);//如果最小的不是父节点，则更换父节点
}
void up(int x){
while(x>>1&&h[x]<h[x>>1]) swap(h[x],h[x>>1]), x>>=1;
}
int main(int argc, char** argv) {
cin>>n>>m;
size=n;
for(int i=1;i<=n;i++) scanf("%d",&h[i]);//输入点
for(int i=n>>1;i;i--) down(i);//桶排序，该更新方式2N时间复杂度
for(int i=0;i<m;i++){//第几小输出
printf("%d ",h[1]);
h[1]=h[size--];//把根（最小点）更换成尾节点，然后down刷新
down(1);
}
printf("\n");
return 0;
} 
查看13道真题和解析
