大根堆

public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> ans;
        int n = input.size();
        if(k > n) return ans;
        priority_queue<int> max_heap;    // 创建最大堆

        for(int i = 0; i < input.size(); i++){
            if(max_heap.size() < k) max_heap.push(input[i]);    // 堆的大小不足k
            else{
                if(max_heap.size() && input[i] < max_heap.top()){    // 堆若不空, 则把当前元素与堆顶比较
                    max_heap.pop();
                    max_heap.push(input[i]);
                }
            }
        }

        while(max_heap.size()){        // 取出堆中的k个元素
            ans.push_back(max_heap.top());
            max_heap.pop();
        }

        return ans;
    }
};