描述

基本解释都在代码中，应该看着通俗易懂。如有错误，欢迎指出。

import java.util.*;

public class Main {
    static int N = 100010;
    // size 存放大小
    static int size = 0;
    // h代表堆
    static int[] h = new int[N];

    // down操作是看一个元素是否需要往下移动
    static void down(int u) {
        int t = u;
        // 如果左儿子存在 并且 左儿子比根节点小， 就使 t 保存 左儿子下标
        if(u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
        // 如果右儿子存在 并且 右儿子比t所代表的值小， 就使 t 保存右儿子下标
        if(u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
        // 如果t发生了变化，说明需要就行交换
        if(t != u) {
            int x = h[t];
            h[t] = h[u];
            h[u] = x;

            // 继续这个过程，看是否需要向下移动
            down(t);
        }
    }

    static void up(int u) {
        // 只要根节点存在，并且u这个节点的值 比 根节点小，就需要交换
        while(u / 2 != 0 && h[u] < h[u / 2]) {
            int t = h[u / 2];
            h[u / 2] = h[u];
            h[u] = t;

            // 继续，看是否还需要向上交换
            u /= 2;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        // 下标从1开始，是为了容易求左右儿子节点的下标
        for(int i = 1; i <= n; i ++) h[i] = sc.nextInt();
        // 令大小等于n
        size = n;

        /* 从二分之n的节点开始就行建立堆，可以让操作达到O(n)
         * 从第二分之n的节点，就是从倒数第二层开始，倒数第二层(down 1层)，倒数第三层(down 2层)，倒数第四层(down 3层)，
         * (n*1/4 + n*2/8 + n*3/16 + ....) < n
         * 为什么这样做能形成正确的堆？？原因：
         *  最后一层元素是堆(因为每个堆只有一个)，然后从倒数第二层开始，保证每一个元素和下一层的其子节点保证是堆
        */
        for(int i = n / 2; i != 0; i --) down(i);

        while(m -- > 0) {
            System.out.print(h[1] + " ");
            // 移除堆顶的元素，就是让最后一个元素覆盖堆顶元素，同时对堆顶元素进行down操作
            h[1] = h[size --];
            down(1);
        }
    }
}