图片说明

利用堆排序输出前n小的数 建堆 down操作

import java.util.*;

public class Main{
    static int m;
    static int n;
    static int size;
    static int[] h;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        size = n;
        h = new int[n + 1];

        for(int i = 1; i <= n; i ++)h[i] = sc.nextInt();//注意下标从一开始
        for(int i = n / 2; i >= 1; i --)down(i);//因为堆是一颗完全二叉树,len/2是最后一个非叶节点，只有最后一个非叶节点才有可能有左右孩子，才能进行down操作
        while(m -- > 0){
            System.out.print(h[1] + " ");
            //因为数组直接删掉头节点后续操作比较麻烦，所以将尾节点赋值成头节点。
            //删除size -- 既删除尾节点。最后头节点down即可
            h[1] = h[size --]; 
            down(1);
        }
    }
    public static void down(int u){
        int t = u;////t是为了找出u和u的左右子树中最小的节点
        if(u * 2 <= size && h[t] > h[2 * u])t = u * 2;;//存在左儿子
        if(u * 2 + 1 <= size && h[t] > h[2 * u + 1])t = u * 2 + 1;//存在右儿子
        if(u != t){ //u不是最小位置位置需要下沉交换两值
            int tmp = h[u];
            h[u] = h[t];
            h[t] = tmp;

            down(t);
        }
    }
}

up操作

public void up(int u){
    while(u / 2 > 0 && h[u / 2] > h[u]){
            int tmp = h[u / 2];
            h[u / 2] = h[u];
            h[u] = tmp;
            u /= 2;
    }
}