Acwing---838. 堆排序

1.题目

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

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

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

数据范围
$1\le m\le n\le 10^5，$

$1\le 数列中元素\le 10^9$

输入样例：

5 3
4 5 1 3 2

输出样例：

1 2 3

2.基本思想

• 如何手写一个堆？完全二叉树 5个操作

1. 插入一个数 heap[ ++ size] = x; up(size);
2. 求集合中的最小值 heap[1]
3. 删除最小值 heap[1] = heap[size]; size -- ;down(1);
4. 删除任意一个元素 heap[k] = heap[size]; size -- ;up(k); down(k);
5. 修改任意一个元素 heap[k] = x; up(k); down(k);

3.代码实现

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

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

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        for (int i = 1; i <= n; i++) h[i] = sc.nextInt();
        size = n;//初始化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);
        }
    }

    private static void down(int u) {
        int min = u;//存储三个结点中存在的最小的结点的下标，初始化为当前结点min
        if (u * 2 <= size && h[u * 2] < h[min]) min = u * 2;//左子节点存在并且小于当前结点，更新min的下标
        if (u * 2 + 1 <= size && h[u * 2 + 1] < h[min]) min = u * 2 + 1;//右子节点存在并且小于当前结点，更新min的下标
        if (min != u) {//如果min==u意味着不用变动，u就是三个结点中拥有最小值的结点下标，否则交换数值
            int temp = h[min];
            h[min] = h[u];
            h[u] = temp;
            down(min);//交换数值后，min这个结点存储原本u的值，u存储存储min的值（三个数中的最小值）。u不用调整了，但min情况不明，可能需要调整。直到它比左右子节点都小
        }
    }
}