题解 | #最小的K个数#

import java.util.ArrayList;
//实际就是使用堆排序，然后将前k个保存到list中。
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        if(input.length<=0||input == null || input.length<k)
            return list;
        //第一步：从最后一个非叶子节点（input.length/2-1）开始，依次从后往前遍历调整，
        //生成一个大顶堆
        for(int i = input.length/2-1;i>=0;i--){
            adjustHeap(input, i, input.length);
        }
        //依次将堆中最后一个元素和堆顶交换，然后将剩余yuan调整成大顶堆，遍历一遍后排序完成
        for(int j=input.length-1;j>0;j--){
            swap(input,0,j);
            adjustHeap(input,0,j);
        }
        //list保存前k个数
        for(int m=0;m<k;m++){
            list.add(input[m]);
        }
        return list;
    }

    //调整大顶堆过程
    public void adjustHeap(int[] input, int pos,int length){
        int temp = input[pos];
        //从pos的左孩子开始，每次都对左孩子操作
        for(int k = 2*pos+1; k<length; k=2*k+1){
            //左孩子和右孩子比较，如果右孩子大就移到右孩子上
            if((k+1)<length && input[k]< input[k+1]){
                k++;
            }
            //当前节点和父节点比较，大的值赋给父节点，同时移动到子节点上
            if(input[k]>temp){
                input[pos] = input[k];
                pos = k;
            }else{
                break;
            }
        }
        //将旧节点的值赋给新节点（和上面联系起来，相当于交换值）
        input[pos] = temp;
    }

    //交换方法
    public void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}