c++ - 优先队列不排序

Question

我正在尝试实现我自己的霍夫曼编码算法，但 C++ STL 的优先级队列似乎无法正常工作。我从字符串中提取字符，并按照它们在字符串中出现的频率顺序将它们插入到优先级队列中。代码编译和运行没有错误，唯一的问题是树似乎没有正确排序。这是代码，

class Node {
 public:
  int freq;
  char data;
  Node(int &f, char &d) { freq=f; data=d; }
  bool operator<(const Node* &n) const { return n->freq < this->freq; }
};

void Init(priority_queue<Node*> &tree, string input) {
 map<char,int> probability;
 for(int i=0 ; i<input.size() ; i++) {
   probability[input[i]]++;
 }
 map<char,int>::iterator it = probability.begin();
 for(it ; it != probability.end() ; it++) {
   Node* blah = new Node(it->second, (char&) it->first);
   tree.push(blah);
 }

我做错了什么？

谢谢

Answer 1

您将指针存储在 priority_queue 中，所以元素按指针值排序，而不是使用你的 operator<过载。

您要么需要存储 Node优先级队列中的对象，或者您需要为优先级队列编写自定义比较函数，取消引用存储的指针并比较 Node他们指向的对象。

既然你问“我做错了什么？”，这里有一些其他建议:

• 你的 operator<重载应该采用 const 引用，而不是对指针的引用。
• 你的 Node构造函数应该按值获取其参数，或者至少按常量引用。 Actor (char&)it->first不好。让const帮助你写出好的代码，不要与之抗争。
• 您可能应该存储 Node直接在优先级队列中的对象，而不是指针。
• 您正在使用 using namespace std某处;你应该删除它并拼出std::无论你需要什么。