Use Priority Queue to find k largest/smallest elements from a sequence

/*

 * Internally Priority queue is implemented as a min_heap

 * so we can utilize the min_heap's properties to implement our code

*/



#include <iostream>

#include <queue>

#include <vector>



using namespace std;



void k_largest(vector<int> a, int n, int k){   

    int i;

    vector<int> ans;

    priority_queue<int, vector<int>, greater<int>> p;     // this is a min_heap

  

  

    for(i=0;i<k;i++)

        p.push(a[i]);

    //cout<<p.top()<<endl;

    for(i=k; i<n; i++)

        if(a[i]>(p.top())){

            p.pop();

            p.push(a[i]);

       }

  

    for(; !p.empty(); p.pop())

        ans.push_back(p.top());

      

  

    for(i=0;i<(int)ans.size();i++)

        printf("%d ",ans[i]);

    puts("");

}



int main(){

    vector<int> a{6, 7, 2, 3, 5, 1, 8, 4, 10};

    int len = a.size();

    int k = 3;

    k_largest(a, len, k);

    return 0;

}