题目
应知必会
堆排序的重点,就是down(),up()函数
void down(int u){
int min = u;
if(u * 2 <= size && h[u * 2] < h[min]) min = u * 2;
if(u * 2 + 1 <= size && h[u * 2 + 1] < h[min]) min = u * 2 + 1;
if(u != min){
int t = h[min];
h[min] = h[u];
h[u] = t;
down(min);
}
}
up()较为简单
void up(int u){
while(u / 2 && h[u / 2] > h[u]){
int t = h[u / 2];
h[u / 2] = h[u];
h[u] = t;
u /= 2;
}
}
完整代码
#include<stdio.h>
#define N 100010
int h[N],size;
void down(int u){
int min = u;
if(u * 2 <= size && h[u * 2] < h[min]) min = u * 2;
if(u * 2 + 1 <= size && h[u * 2 + 1] < h[min]) min = u * 2 + 1;
if(u != min){
int t = h[min];
h[min] = h[u];
h[u] = t;
down(min);
}
}
void up(int u){
while(u / 2 && h[u / 2] > h[u]){
int t = h[u / 2];
h[u / 2] = h[u];
h[u] = t;
u /= 2;
}
}
int main(){
int n,m;scanf("%d%d",&n,&m);
size = n;//不要忘记
for(int i = 1;i <= n;i ++ ) scanf("%d",&h[i]);//为了方便(左右儿子的计算),从1开始
for(int i = n / 2;i;i -- ) down(i);//堆排序
while(m -- ){
printf("%d ",h[1]);//头节点即最小值
h[1] = h[size -- ];//删除堆顶(用最后一个数覆盖第一个数) 并且长度减1
down(1);//让覆盖好的数往下面走,确保头节点是最小值
}
return 0;
}