算法题---求最大前K及最小前K的数的代码

 使用堆排序

大顶堆解决最小前K的问题

小顶堆解决最大前K的问题

c++中使用优先队列priority_queue构造堆，支持以下操作

1. empty() : 如果优先队列为空，返回真
2. pop() : 删除第一个元素
3. push() : 加入一个元素
4. size() ： 返回优先队列中拥有的元素的个数
5. top() : 返回优先队列中最高优先级的元素，即堆顶元素

大顶堆c++ 实现 ： priority_queue<int> q;

小顶堆c++实现 ： priority_queue<int, vector<int>, greater<int> > q;

求最小前K个数（大顶堆）

class Solution {
public:
    vector<int> smallestK(vector<int>& arr, int k) {
        
        priority_queue<int> q;
        vector<int> res;
        int size = arr.size();

        if(k == 0 || size == 0) return vector<int> ();

        for(int i=0; i<k; i++){
            q.push(arr[i]);
        }
        
        for(int i=k; i<size; i++){
            if(arr[i] < q.top()){
                q.pop();
                q.push(arr[i]);
            }
        }

        while(!q.empty()){
            res.push_back(q.top());
            q.pop();
        }
        return res;
    }
};

求最大前K个数(小顶堆）

class Solution {
public:
    vector<int> smallestK(vector<int>& arr, int k) {
        
        priority_queue<int, vector<int> greater<int> > q;
        vector<int> res;
        int size = arr.size();

        if(k == 0 || size == 0) return vector<int> ();

        for(int i=0; i<k; i++){
            q.push(arr[i]);
        }
        
        for(int i=k; i<size; i++){
            if(arr[i] > q.top()){
                q.pop();
                q.push(arr[i]);
            }
        }

        while(!q.empty()){
            res.push_back(q.top());
            q.pop();
        }
        return res;
    }
};