incorrect output min stl priority queue for printing top 'm' elements

Question

min stl priority queue for storing top 'm' elements out of the entire array is showing an incorrect output. Here in this example, the sorted vector will be [1,3,3,3,3,5,5,5,5,8,8,8,8,8]. Thus the top 'm' where m = 5 should be 1,3,3,3,3 but the output is 1,3,3,3,5. Could anyone suggest why it is not working in case of duplicate entries. Here is the sample code.

#include <iostream>  
#include <queue>  
using namespace std;  

 struct compare  
 {  
   bool operator()(const int& l, const int& r)  
   {  
       return l > r;  
   }  
 };  

 int main()  
 {  
     priority_queue<int,vector<int>, compare > pq;  
    vector <int> p;
     p.push_back(3);  
     p.push_back(3);  
     p.push_back(3);  
     p.push_back(3);  
     p.push_back(5);  
     p.push_back(5);  
     p.push_back(5);  
     p.push_back(5);  
     p.push_back(1);  
     p.push_back(8);  
     p.push_back(8);  
     p.push_back(8);  
     p.push_back(8);  
     p.push_back(8); 
    for(int i=0;i<p.size();i++)
{
        int k= p[i];
        if(pq.size() < 5) // top 'm' elements say m = 5 here 
                {
                        pq.push(k);
                }
                else if (pq.top() >= k)
                {
                        pq.pop();
                        pq.push(k);
                }
 }

     while ( !pq.empty() )  
     {  
         cout << pq.top() << endl;  
         pq.pop();  
     }  
     cin.get();  
 }

The incorrect output is :

1
3
3
3
5

but the correct output should be

1
3
3
3
3

Answer 1

The priority queue defined by you is actually pushing values from lowest to highest from top to bottom till the point in code when priority queue size <= 5, but after that it is replacing the currently-lowest value in PQ (equals top of PQ) with the new lowest value to be pushed. Consequently, you are losing the second lowest value in resulting PQ.

Instead of replacing the lowest value with second lowest, you should be pushing out the highest one (the bottom-most in PQ), which is not possible IMO without using double queue (or stack) implementation, and also not recommended for higher time complexity.

Solution:

Change the definition of pq from

priority_queue<int,vector<int>, compare > pq;

to

priority_queue<int,vector<int>> pq;

Get the reverse of PQ to get the answer :

Do list::push_front(pq.top) and pop elements in PQ till PQ becomes empty, and then print the list using

 for (std::list<int>::iterator it=mylist.begin(); it!=mylist.end(); ++it)
    std::cout << ' ' << *it <<endl;

Find working code here