AcWing 838. 堆排序(JAVA)
原题链接
简单
作者:
鼠鼠我
,
2021-02-01 23:46:46
,
所有人可见
,
阅读 337
import java.util.Scanner;
//堆排序从1开始,上面的根节点从1开始
//因为左儿子等于2*x,右儿子等于2*x+1
//
//小顶堆
//head 代表堆(一维数组来模拟堆,下标i的左子树是2i,右子树是2i+1)
//uo(i) 代表该下标的点,向上移动,直到找到他的位置
//down(i) 代表该下标的点,向下移动,直到找到他的位置
//
// 插入一个数 head[ ++ size] = x; up(size);
// 取出最小值 head[1];
// 删除最小值 head[1] = head[size]; size–; down(k);
// 修改任意的数 head[k] = x; size–; down(k); up(k)
// 删除任意的数 head[k] = head[size]; size–; down(k); up(k)
public class Main {
static int[] h = new int[100010];//堆数组
static int size;//堆中点的数目
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
for(int i=1;i<=n;i++) h[i] = sc.nextInt();
size = n;
for(int i=n/2;i!=0;i--) down(i);//建堆
while(m-->0)
{
System.out.print(h[1]+" ");
h[1] = h[size];
size--;
down(1);
}
}
static void down(int u)//上面是最小的数,替换上来的数向下找比他小的值替换
{
int t = u;//t存的是三个点里面的最小值
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)
{
swap(u,t);
down(t);
}
}
static void swap(int a,int b)
{
int temp=h[a];
h[a] = h[b];
h[b] = temp;
}
}