题解 | #最小的K个数#

import java.util.ArrayList;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        // 堆排序可以找出前最小的k的数，最小堆
        return heapSort(input, k);
    }

    public ArrayList<Integer> heapSort(int[] arr, int k){
        ArrayList<Integer> list = new ArrayList<>();
         if(arr.length==0)
            return list;
        // 创建初始堆
        for(int i=(arr.length-1)/2;i>=0;i--){
            // 从第一个分支节点开始
            adjustHeap(arr,i, arr.length);
        }

        // 调整堆结构，交换前K个数
        for(int i=arr.length-1;i>arr.length-1-k;i--){
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            list.add(arr[i]);

            adjustHeap(arr, 0, i);
        }
        return list;
    }

    public void adjustHeap(int[] arr, int n, int length){
        int temp = arr[n];
        int lchild = 2 * n + 1; // 左孩子
        while(lchild < length){
            int rchild = lchild + 1; // 获取右孩子
            if(rchild < length && arr[lchild] > arr[rchild]){
                // 如果右孩子存在且左孩子大于右孩子
                lchild++;
            }
            // 如果父节点小于左右孩子中较小的那个，则跳过
            if(temp < arr[lchild]){
                break;
            }
            arr[n] = arr[lchild];
            arr[lchild] = temp;

            n = lchild;
            lchild = 2 * lchild + 1; // 交换了之后仍然要比较子节点
        }
    }
}