AcWing 838. 堆排序--详解
原题链接
简单
作者:
Violet_66
,
2023-05-08 21:08:02
,
所有人可见
,
阅读 132
堆的每个结点都是小于左右儿子的,down是向下调整,up是向上调整,都调整为满足堆条件的样子
思路:将整个数组模拟成堆,每次将堆顶输出,因为堆顶永远是对里面最小的数,所以是正序输出,需要输出最小值 和删除最小值两个操作来完成,只需要down操作
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int n,m;
int h[N],s;
void down(int u){//
int t=u;
//如果一边满足先将t转换为这一边,如果另一边比这个小那说明另一边是两个左右儿子中最小的,实现找到左右儿子中最小的并进行交换的操作
if(u*2 <= s && h[u*2]<h[t]) t=u*2;
if(u*2+1<= s && h[u*2+1]<h[t]) t=u*2+1;
if(u != t){//当上面两个判断都不满足的时候,就不需要在进行判断了,此时的堆数组已经满足条件了
swap(h[u],h[t]);
down(t);
}
}
void up(int u){
while(u/2 && h[u/2]>h[u]){
swap(h[u/2],h[u]);
u /=2;
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>h[i];
s=n;
for(int i=n/2;i;i--) down(i);//先将给定数列进行堆排序
while(m--){
cout<<h[1]<<" ";
h[1]=h[s];
s--;
down(1);
}
return 0;
}