Очередь приоритетов C ++ «больше» опция не работает
В чем проблема?
Когда я использую приоритетную очередь STL, я хочу использовать min heap, поэтому я использовал следующий код.
Он работает по умолчанию, но не работает на «большой вариант».
Это всегда устраивает, как на картинке выше. Я не знаю полностью, почему это произошло.
struct node {
string code;
int fre;
bool operator<(const node& rhs) const {
return fre < rhs.fre;
}
bool operator>(const node& rhs) const {
return fre > rhs.fre;
}
};
std::priority_queue<node, vector<node>, greater<node>> q;
std::map<node,int> huffman_tree;
int main(void)
{
int f;
for (int i = 1; i <= n; i++) {
string c;
std::cin >> c >> f;
node huffman = { c,f };
q.push(huffman);
}
q.pop();
return 0;
}
Решение
Если я правильно понимаю вашу проблему, вы просматриваете приоритетную очередь в отладчике и не понимаете, почему элементы в очереди не хранятся в том порядке, в котором вы ожидали.
Приоритетные очереди не гарантируют хранение элементов в приоритетном порядке. Они гарантируют, что вернут вам предметы только в порядке очередности, когда вы вытаскиваете их из очереди. Хранение элементов в порядке приоритета будет означать, что ему придется выполнять операцию сортировки каждый раз, когда новый элемент помещает в очередь, что будет неэффективно. Вместо этого приоритетные очереди обычно используют структуру данных, называемую кучей, для управления очередью, что позволяет гораздо более эффективно вставлять в очередь.
Другие решения
Других решений пока нет …