堆排序

import java.io.*;
public class Main{
    //通过数组模拟堆
    static int N=100010;
    static int[] heap=new int[N];
    static int size=0;
    public static void main(String[] args)throws IOException{
        BufferedReader cin=new BufferedReader(new InputStreamReader(System.in));
        String[] str=cin.readLine().split(" ");
        int n=Integer.parseInt(str[0]);int m=Integer.parseInt(str[1]);
        //将所有的元素存到数组
        String[] s=cin.readLine().split(" ");
        for(int i=0;i<n;i++){
            heap[i+1]=Integer.parseInt(s[i]);
        }
        size=n;//当前堆中的元素个数
        for(int i=n/2;i>0;i--){
            down(i);
        }

        for(int i=0;i<m;i++){
            System.out.print(heap[1]+" ");
            heap[1]=heap[size--];
            down(1);
        }

    }
    public static void up(int u){
        while(u/2>0&&heap[u/2]>heap[u]){
            swap(heap,u/2,u);
            u/=2;
        }
    }
    public static void down(int u){
        int t=u;
        if(u*2<=size&&heap[u*2]<heap[t]){
            t=u*2;
        }
         if(u*2+1<=size&&heap[u*2+1]<heap[t]){
            t=u*2+1;
        }
        if(u!=t){
            swap(heap,u,t);
            down(t);
        }
    }
    // public static void insert(int x){

    // }
    // public static int getTop(){

    //     return 0;
    // }
    // public static void extract(){

    // }
    // public static void remove(int k){

    // }

    public static void swap(int[] heap,int i,int j){
        int t=heap[i];
        heap[i]=heap[j];
        heap[j]=t;
    }
}