题解 | #最小的K个数#

构建小根堆，然后取 k 次根，每次取完后再堆化

import java.util.ArrayList;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<>();
        buildHead(input,input.length);
        for (int i = 1; i <= k; i++) {
            res.add(input[0]);
            swap(input,0,input.length-i);
            heapify(input,0,input.length-i);
        }
        return res;
    }

    // 建堆
    public void buildHead(int[] arr,int n) {
        for (int i = (n/2)-1; i >=0; i--) {
            heapify(arr,i,n);
        }
    }

    // 堆化
    public void heapify(int[] arr,int i,int n) {
        while (i*2+1<n) {
            int child = i * 2 + 1;
            if (child+1<n && arr[child+1]<arr[child]) child++;
            // 说明堆化完成了，不用再进行了
            if (!(arr[child] <arr[i])) return;
            swap(arr,i,child);
            i=child;
        }
    }

    public void swap(int[] arr,int x,int y) {
        int tmp = arr[x];
        arr[x]=arr[y];
        arr[y]=tmp;
    }
}