AcWing 838. 堆排序--Java详细注解
原题链接
简单
作者:
OneDay1
,
2021-03-09 17:16:54
,
所有人可见
,
阅读 312
import java.util.*;
import java.io.*;
public class Main{
static int N = 100010;
// 定义堆
static int[] h = new int[N];
// 确定堆的大小
static int size;
// 当数在三个数中大时,使数往下沉
public static void down(int u){
// 设三个数的最小值为t;
int t = u;
// u*2为 u的左儿子; u*2+1 为u的右儿子;
// 如果左儿子的下标小于堆的大小,则表示存在这个点;
// 并且左儿子值比最小t的值小,则将t指向左儿子
if(u*2 <= size && h[u*2] < h[t]) t = u * 2;
// 如果右儿子的下标小于堆的大小,则表示存在这个点;
// 并且右儿子值比最小t的值小,则将t指向右儿子
if(u*2+1 <= size && h[u*2+1] < h[t]) t = u*2+1;
// 如果最后t的最小值不是自己(u);
// 那么交换两个下标所在的值;交换完在down一下,防止破坏堆结构;
if(t != u){
int temp = h[u];
h[u] = h[t];
h[t] = temp;
down(t);
}
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] s = br.readLine().split(" ");
int n = Integer.parseInt(s[0]);
int m = Integer.parseInt(s[1]);
String[] str = br.readLine().split(" ");
// 初始化堆
for(int i = 1; i <= n; i++){
h[i] = Integer.parseInt(str[i-1]);
}
// 设置堆的大小
size = n;
// 建堆-->时间复杂度为O(n);
for(int i = n/2;i != 0;i--){
down(i);
}
while(m-- != 0){
// 输出最当前最小值,也就是堆顶
bw.write(h[1]+" ");
// 将最后的值覆盖掉堆顶--就是删掉堆顶
h[1] =h[size];
// 堆大小--
size--;
// 在把堆顶down一下 找出最小值;
down(1);
}
bw.flush();
br.close();
bw.close();
}
}