C++ 优先级队列 "greater" 选项不起作用
C++ priority queue "greater" option is not working
What is the problem?
When I use priority queue of STL, I want to use min heap, so I used like below code.
It works on default option but it is not working on "greater option".
总是像上图这样排列。我完全不知道为什么会这样。
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;
}
如果我对你的问题的理解正确,那么你正在调试器中查看优先级队列并且对为什么队列中的项目没有按照你期望的顺序存储感到困惑。
优先队列不保证按优先顺序存储项目。他们只保证在您将物品从队列中取出时按优先顺序归还给您。保持项目的优先顺序意味着每次将新项目放入队列时都必须执行排序操作,这将是低效的。相反,优先级队列通常使用称为堆的数据结构来管理队列,这允许更有效地插入队列。
What is the problem?
When I use priority queue of STL, I want to use min heap, so I used like below code.
It works on default option but it is not working on "greater option".
总是像上图这样排列。我完全不知道为什么会这样。
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;
}
如果我对你的问题的理解正确,那么你正在调试器中查看优先级队列并且对为什么队列中的项目没有按照你期望的顺序存储感到困惑。
优先队列不保证按优先顺序存储项目。他们只保证在您将物品从队列中取出时按优先顺序归还给您。保持项目的优先顺序意味着每次将新项目放入队列时都必须执行排序操作,这将是低效的。相反,优先级队列通常使用称为堆的数据结构来管理队列,这允许更有效地插入队列。