class Solution {
public:
    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
        //开一个大小为k的大顶堆，放入堆
        //如果当前堆元素大于k，弹出，最后输出堆中元素即可
        //时间复杂度为Nlogk
        priority_queue<int> heap;
        vector<int> res;
        if(input.empty()) return res;
        for(auto x:input){
            heap.push(x);
            if(heap.size() > k) heap.pop();
        }

        while(heap.size()){
            res.push_back(heap.top());
            heap.pop();
        }

        reverse(res.begin(),res.end());
        return res;
    }
};