AcWing 838. 堆排序(Java + 详解)
原题链接
简单
作者:
Wonion
,
2021-01-16 23:39:56
,
所有人可见
,
阅读 379
代码
/*时间复杂度 插入和删除都是logN 查找最小值是1 */
import java.util.Scanner;
public class Main{
static int N = 100010;
static int[] h = new int[N]; //储存堆中的值,左儿子是2x,右儿子是2x + 1
static int size = 0; //堆的大小
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
for(int i = 1; i <=n; i ++) h[i] = in.nextInt(); //注意从1开始存储
size = n;
for(int i = n / 2; i != 0; i --) down(i); //建堆,必须要从非叶子节点开始down,因为最后一层是不需要的
while(m-- > 0)
{
System.out.print(h[1] + " ");
h[1] = h[size--]; //删除最小值,然后继续向下沉,保证h[1]永远是最小的
down(1);
}
}
private static void down(int u) //t表示移动后的节点,u表示移动前的节点
{
int t = u;
if(u * 2 <= size && h[u * 2] < h[t]) t = u * 2; //注意这里一定要先和左节点比较,在和右节点比较
if(u * 2 + 1 <= size && h[u *2 + 1] < h[t]) t = u * 2 + 1;
if(u != t) //说明发生移动了,就交换两者的位置
{
int a = h[u];
h[u] = h[t];
h[t] = a;
down(t); //交换完后就继续向下走
}
}
}