题目描述

输入一个长度为n的整数数列，从小到大输出前m小的数。

输入格式
第一行包含整数n和m。

第二行包含n个整数，表示整数数列。

输出格式
共一行，包含m个整数，表示整数数列中前m小的数。

数据范围
1≤m≤n≤105，
1≤数列中元素≤109
输入样例：

5 3
4 5 1 3 2

输出样例：

1 2 3

算法1

思路

1.先构造小根堆！！

2.弹出最小值pop：先取出h[1]，最后一个位置的值覆盖到1位置，size–

ps：下标从1开始，方便左右子节点坐标表示

时间复杂度

构造堆:O(N)
弹出最小值：O(logN)

Java 代码

import java.util.*;

public class Main{
    private static int N = 100010;
    private static int[] h = new int[N];
    private static int size = 0;

    public static void down(int i){
        int min = i;
        //注意：这里要用下标位置和size比较！！！！
        //如果用值和0比较的话会下标越界(必须扩容)且pop最后1个数覆盖到1位置后要清0
        if(i * 2 <= size && h[i * 2] < h[min]){
            min = i * 2;
        }
        if(i * 2 + 1 <= size && h[i * 2 + 1] < h[min]){
            min = i * 2 + 1;
        }
        if(min != i){
            swap(min,i);
            down(min);
        }
    }
    public static int pop(){
        int t = h[1];
        h[1] = h[size--];
        down(1);
        return t;
    }
    public static void swap(int i ,int j){
        int t = h[i];
        h[i] = h[j];
        h[j] = t;
    }
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        for(int i = 1;i <= n;i++){
            h[i] = scanner.nextInt();
        }
        size = n;
        //构造堆：从倒数第二层最后一个位置开始往前down()
        for(int i = n/2;i > 0;i--){
            down(i);
        }
        while(m-- > 0){
            System.out.print(pop() + " ");
        }
    }
}