题目描述

输入一个长度为 n 的整数数列，从小到大输出前 m小的数。
输入格式
第一行包含整数 n和 m。
第二行包含 n个整数，表示整数数列。
输出格式
共一行，包含 m个整数，表示整数数列中前 m小的数。
数据范围
1≤m≤n≤105，1≤数列中元素≤109

输入样例：

5 3
4 5 1 3 2

输出样例：

1 2 3

package java002;

import java.util.Scanner;
//堆操作
public class Main8 {
    static int N=100010;
    static int[] h=new int[N];
    static int size=0;
    static int[] ph=new int[N];
    static int[] hp=new int[N];
    public static void main(String[] args) {
        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);
        }
        //输出前m小的数
        //覆盖+下沉
        while (m-->0) {
            System.out.print(h[1]+" ");
            h[1]=h[size];//覆盖
            size--;//删除尾节点
            down(1);//下沉
        }

    }
    public static void down(int u) {
        //判断左右孩子节点
        int t=u;//3个点中的最小值t
        if (u*2<=size && h[u*2]<h[t]) {//如果左孩子存在，左孩子比最小值还小,那么
            t=2*u;
        }
        if (u*2+1<=size && h[2*u+1]<h[t]) {//同理
            t=2*u+1;
        }
        //如果根节点比最小值要大，交换
        if (u!=t) {
            swap(t, u);
            down(t);
        }

    }
    //swap交换函数
    public static void swap(int a,int b) {
        int sp=h[a];
        h[a]=h[b];
        h[b]=sp;
    }
}