题解 | #最小的K个数#

package org.example.test;

import com.alibaba.fastjson.JSONObject;

import java.util.ArrayList;

/**
 * 首先使用大小为K的数组，读入钱K个数，建立大顶堆。
 * 然后一次读入余下的数，若大于大顶堆，则舍弃，否则用改数取代堆顶并重新调整堆，待数据读取完毕，
 * 堆中K个数即为所求
 */
public class HeapTest {

    public static void main(String[] args) {
        int[] input = {4,5,1,6,2,7,3,8};
        System.out.println(JSONObject.toJSONString(GetLeastNumbers_Solution(input, 4)));
    }
    public static ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        ArrayList<Integer> ret = new ArrayList<>();
        if (k==0){
            return ret;
        }
        ret.add(0);
        for (int i = 0; i < k; i++) {
           ret.add(input[i]);
        }
        for (int i = k / 2; i > 0; i--) {
            headAdjust(ret, i, k);
        }
        for (int i = k ; i < input.length; i++) {
            if (ret.get(1) > input[i]) {
                ret.set(1, input[i]);
                headAdjust(ret, 1, k);
            }
        }
        ret.remove(0);
        return ret;
    }

    private static void headAdjust(ArrayList<Integer> heap, int i, int len) {
        heap.set(0, heap.get(i));
        for (int j = 2 * i; j <= len; j *= 2) {
            if (j < len && heap.get(j) < heap.get(j + 1)) {
                j++;
            }
            if (heap.get(0) >= heap.get(j)) {
                break;
            } else {
                heap.set(i, heap.get(j));
                i = j;
            }
        }

         heap.set(i, heap.get(0));
    }

}