用于打印顶部 'm' 元素的输出最小 stl 优先级队列不正确

Question

min stl 优先级队列用于存储整个数组中的前 'm' 个元素显示不正确的输出。在此示例中，排序后的向量将为 [1,3,3,3,3,5,5,5,5,8,8,8,8,8]。因此顶部 'm' 其中 m = 5 应该是 1,3,3,3,3 但输出是 1,3,3,3,5。谁能建议为什么在重复条目的情况下它不起作用。这是示例代码。

#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();  
 }

错误的输出是：

但正确的输出应该是

Answer 1

当 if(pq.size() < 5) 在 p 上的迭代中，您用

填充 pq

 3 3 3 3 5

之后 else if (pq.top() >= k) 条件完成工作，您将 top 值 3 替换为 p 中的最小值。是 1。所以你终于得到了：

 1 3 3 3 5

Answer 2

你定义的优先级队列实际上是将值从最低推到最高从top到底部直到点在优先级队列 size <= 5、but 之后的代码中 replacing PQ 中的当前最低值（等于 PQ 的顶部）使用 new 要推送的最低值。因此，您 失去了结果 PQ 中第二低的 值。

而不是用第二低的值替换最低值，你应该推出最高的值（PQ 中的最底部），如果不使用双队列（或堆栈）实现，这是不可能的 IMO，而且也不是推荐用于更高的时间复杂度。

解法：

将 pq 的定义从

更改为

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

至

priority_queue<int,vector<int>> pq;

PQ取反得到答案 :

做list::push_front(pq.top)弹出PQ中的元素直到PQ变空，然后使用

打印列表

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

查找working code here

Answer 3

如果您的目标是查找并存储向量的前 5 个元素，请考虑使用 std::partial_sort_copy 而不是 priority_queue:

std::array<int, 5> arr;
std::partial_sort_copy(p.begin(), p.end(), arr.begin(), arr.end());

这样您就可以将前 5 个元素存储在 arr 中。

旁注：您可以使用初始化列表在一行中设置向量

vector <int> p{3,3,3,3,5,5,5,5,1,8,8,8,8,8};

Working code example

Answer 4

您可以执行以下操作

int main()  
{  
    std::priority_queue<int, std::vector<int>, std::less<>> pq;

    for(int i : {3, 3, 3, 3, 5, 5, 5, 5, 1, 8, 8, 8, 8, 8}) {
        if (pq.size() < 5 || i < pq.top()) {
            pq.push(i);
        }
        if (pq.size() > 5)
        {
            pq.pop();
        }
    }
    while (!pq.empty()) {  
        std::cout << pq.top() << std::endl;  
        pq.pop();  
    }  
}

有反转显示。

用于打印顶部 'm' 元素的输出最小 stl 优先级队列不正确

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

c++

stl

priority-queue