// 堆的做法：
// 集合的大小是k，每次会插入n个数，所以nlogk
// 堆顶是最大的数，如果新来的数很大，那么插入堆之后删除的也是他，如果新来的小，那么就会删除掉最大的数

class Solution {
public:
    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
        priority_queue<int> heap;
        for(auto c:input)
        {
            heap.push(c);
            if(heap.size()>k) heap.pop();
        }
        vector<int> res;
        while(heap.size()) res.push_back(heap.top()),heap.pop();
        reverse(res.begin(),res.end());
        return res;
    }
};