class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        //思路：建一个小根堆，然后出k次堆顶元素即可，不知道能不能ac
        //首先把给的数组建成一个小根堆
        //数组中i位置上的元素在堆上的父亲位置为（i-1）/2;
        for(int i=1;i<input.size();i++)
        {
            int ans=i;
            while(input[ans]<input[(ans-1)/2])//如果比他父亲还要小则向上调整
            {
                int temp=input[ans];
                input[ans]=input[(ans-1)/2];
                input[(ans-1)/2]=temp;
                ans=(ans-1)/2;//向上调整
            }
        }
        //循环结束后该数组就已经是个小根堆了
        int heapSize=input.size();//heapSize决定小根堆的范围
        vector<int > array;
        for(int i=0;i<k&&heapSize>0;i++)
        {
            array.push_back(input[0]);
            input[0]=input[--heapSize];
            int ans=0;
            while(2*ans+1<heapSize)//即存在左孩子就循环
            {
                int min=(input[2*ans+1]>input[2*ans+2]&&2*ans+2<heapSize)?2*ans+2:2*ans+1;
                if(input[min]<input[ans])
                {
                    int temp=input[ans];
                    input[ans]=input[min];
                    input[min]=temp;
                    ans=min;//向下调整
                }
                else//如果左右孩子中的最小值都比根大则break；
                    break;
            }
        }
        return array;
    }
};