题目描述

堆排序

JAVA 代码

import java.util.*;
import java.io.*;

class Main{

    //初始化 得有个 总长度来判断是否有儿子.
    static int N = 100010, size; 
    static int[] h = new int[N];

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

        //总长度.初始化
        size = n;

        for(int i = 1; i<= n;i++){
            //先讲数字乱序放入数组. 
            h[i] =sc.nextInt();
        }

        //从一半的地方开始维护.因为大的总会沉到最下面去.
        for(int i = n/2; i>0 ; i--){
            down(i);
        }


        while(m-->0){
            //顺序输出.
            System.out.print(h[1] + " ");
            //删除头节点, 用最下的点覆盖最上面的.再沉下来. 
            h[1] = h[size--];
            down(1);
        }
    }
    public static void down(int u){
        //这里t 和 u 都是下标
        int t = u;
        //如果有左儿子的话, 并且左儿子的值大于当前节点. t = 左儿子的下标
        if(u * 2 <= size && h[u*2] < h[t]) t = u*2;
        //如果有右儿子的话, 并且右儿子的值大于当前节点. t = 右儿子的下标
        if(u*2+1 <= size && h[u*2+1] < h[t]) t = u*2+1;
        //如果t 是修改过的
        if(u!=t){
            //交换位置. 
            int temp = h[t];
            h[t] = h[u];
            h[u] = temp;
            //继续下沉.
            down(t);
        }

    }

}