неправильный вывод min stl приоритет для печати верхних 'm' элементов

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

Некорректный выход:

1 
3 
3 
3 
5 

но правильный вывод должен быть

1 
3 
3 
3 
3 

Answer 1

очередь по приоритету определяется вами фактически толкая значение от низкой к высшей от top вниз до точки в коде, когда приоритет очередь size <= 5, но после что это , заменив самым низким значением в PQ (равным вершине PQ) с новым самым низким значением, которое нужно нажать. Следовательно, вы находитесь , теряя второе низшее значение в результате 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 2

Когда if(pq.size() < 5) в вашей итерации над p вы заполните pq с

3 3 3 3 5 

после этого else if (pq.top() >= k) условие выполнит эту работу, и вы замените значение top3 с наименьшим значением в p. Это 1. Так что в конце концов у вас есть:

1 3 3 3 5 

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.

Sidenote: вы можете использовать список инициализации, чтобы настроить свой вектор в одной строке

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

с обратным дисплеем.