知识点补充—堆

小顶堆
head 代表堆（一维数组来模拟堆，下标i的左子树是2i,右子树是2i+1）
uo(i) 代表该下标的点，向上移动，直到找到他的位置
down(i) 代表该下标的点，向下移动，直到找到他的位置

1. 插入一个数 head[ ++ size] = x; up(size);
2. 取出最小值 head[1];
3. 删除最小值 head[1] = head[size]; size–; down(k);
4. 修改任意的数 head[k] = x; size–; down(k); up(k)
5. 删除任意的数 head[k] = head[size]; size–; down(k); up(k)

题目描述

给定n和m两个数，n代表输入n个数，m代表找出n个数中最小的m个依次输出。

输入样例

5 3
4 5 1 3 2

输出样例

1 2 3

算法1

(堆排序) $O(n)$

相当于堆操作中的取出最小值和删除最小值，直接用堆就行

时间复杂度：$O(n)$

参考文献：y总

Java 代码

import java.util.Scanner;

public class Main {
    static int N = 100010;
    static int[] h = new int[N];//用一维数组存储堆
    static int size;// 存储堆的大小

    // 下移 找到u下标的最终位置
    static void down(int u){
        int t = u;
        // 找到t和左右孩子中最小的下标
        if (2 * u <= size && h[2 * u] < h[t]) t = 2 * u;
        if (2 * u + 1 <= size && h[2 * u + 1] < h[t]) t= 2 * u + 1;
        // 将最小下标的值放到u上
        if (t != u){
            int x = h[u];
            h[u] = h[t];
            h[t] = x;
            down(t);
        }
    }

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        String[] s = scan.nextLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);
        s = scan.nextLine().split(" ");
        for (int i = 1; i <= n; i++) h[i] = Integer.parseInt(s[i -1]);
        size = n;

        // 初始化堆 O(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);
        }
    }
}